? 一、数组

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
    vector<vector<int>> ans;//首先创建一个存放一个符合题意的一个三数组
    
    int n=nums.size();      
    if(n<3){            //如果这个数组小于3三个元素 不可能满足
        return {};
    }
    sort(nums.begin(),nums.end());//对这个数组进行排序
    for(int i=0;i<n;i++){               //进入循环 开始 把i当作第一个数  
        if(nums[i]>0){return ans;}      //这是排序过的 如果第一个数大于0 那么后面的数没有负的 就不可能三个数相加等于0；
        if(i>0&&nums[i]==nums[i-1]){continue;}//如果这个数前面用过了 就跳过

        int l=i+1;//左指针
        int r=n-1;//右指针
        // 进入双指针法找到 i后面  两个数之和=-i的；
        while(l<r){
            //如果两数之和大 就要减小 右指针向左收缩
            if(nums[l]+nums[r]>-nums[i]){
                r--;
                
            }
                 //如果两数之和小 就要增加 左指针向右收缩
                else if(nums[l]+nums[r]<-nums[i]){
                l++;
               
            }
                //如果相等     
                else{
                ans.push_back(vector<int>{nums[i],nums[l],nums[r]});//将符合的 三个坐标插入 我们的答案二维数组
                //然后收缩指针 看看 之间还有没有 符合的
                l++;
                r--;
                    
                //在找到相等的情况下，有数字重复就跳过
                while(l<r&&nums[r]==nums[r+1]){ r--; }
                while(l<r&&nums[l]==nums[l-1]){ l++; }
            }
        }
    }
    return ans;
    }
};

16. 最接近的三数之和

难度中等820

给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

示例：

输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
     int n=nums.size();
     sort(nums.begin(),nums.end());
     int l,r,sum,ans=nums[0]+nums[1]+nums[2];
     for(int i=0;i<nums.size()-2;++i){   
        if(i>0 &&nums[i-1] == nums[i]) continue;
        l = i+1; 
        r = n-1;
        while(l<r){
           sum=nums[i]+nums[l]+nums[r] ;   
           if(sum == target) return target;
           if(abs(sum-target)<abs(ans-target)) ans=sum;  
           if(sum>target)r--;
           else l++;
        }  
     }
     return ans;
    }
};

给定 matrix = [
  [3, 0, 1, 4, 2],
  [5, 6, 3, 2, 1],
  [1, 2, 0, 1, 5],
  [4, 1, 0, 1, 7],
  [1, 0, 3, 0, 5]
]

sumRegion(2, 1, 4, 3) -> 8
sumRegion(1, 1, 2, 2) -> 11
sumRegion(1, 2, 2, 4) -> 12

using namespace std;
#include <vector>

class NumMatrix {
private:
    vector<vector<int> > sums;
public:
    NumMatrix(vector<vector<int> >& matrix) {
        int n = matrix.size();
        int m = matrix[0].size();
        if (n == 0 || m == 0) {
            return;
        }

        sums.resize(n + 1, vector<int>(m + 1, 0));
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                sums[i][j] = matrix[i - 1][j- 1] + sums[i - 1][j] + sums[i][j - 1] - sums[i - 1][j - 1];
            }
        }

        return;
    }
    
    int sumRegion(int row1, int col1, int row2, int col2) {
        return sums[row2 + 1][col2 + 1] - sums[row2 + 1][col1] - sums[row1][col2 + 1] + sums[row1][col1];
    }
};

/**
 * Your NumMatrix object will be instantiated and called as such:
 * NumMatrix* obj = new NumMatrix(matrix);
 * int param_1 = obj->sumRegion(row1,col1,row2,col2);
 */

1, 3, 5, 7, 9
7, 7, 7, 7
3, -1, -5, -9

1, 1, 2, 5, 7

A = [1, 2, 3, 4]

返回: 3, A 中有三个子等差数组: [1, 2, 3], [2, 3, 4] 以及自身 [1, 2, 3, 4]。

//dp
class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& nums) {
       int n=nums.size();
       if(n<3) return 0; 
       int sum=0;
       vector<int> dp(n,0);  
       for(int i=2;i<n;++i){
         if(nums[i]-nums[i-1]==nums[i-1]-nums[i-2]) {
           dp[i]=dp[i-1]+1;
           sum+=dp[i];  //前缀和  
         }  
       }
       return sum;
    }
};

//优化dp
class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& nums) {
       int n=nums.size();
       if(n<3) return 0; 
       int sum=0;
       int pre=0; 
       for(int i=2;i<n;++i){
         if(nums[i]-nums[i-1]==nums[i-1]-nums[i-2]) {
           pre=pre+1;
           sum+=pre;    
         }
         else pre=0;  
       }
       return sum;
    }
};