LeetCode 15. 3Sum 16. 3Sum Closest 18. 4Sum-白红宇

LeetCode 15. 3Sum 16. 3Sum Closest 18. 4Sum

阅读量：6566 次

发布时间：2019-06-24

本文共 1286 字，大约阅读时间需要 4 分钟。

n数求和，固定n-2个数，最后两个数在连续区间内一左一右根据当前求和与目标值比较移动，如果sum<target，移动较小数，否则，移动较大数

重复数处理：

使i为左至右第一个不重复数：while(i != 0 && i<n-2 && a[i] == a[i-1]) i++;

使r为右至左第一个不重复数（原序最后一个）：while(r>i && r+1<n && a[r] == a[r+1]) r--;

15. 3Sum

class Solution {public:    vector
     
      
       > threeSum(vector
       
        & nums) {        sort(nums.begin(), nums.end());        vector
        
         
          > ans;        int n = nums.size();        vector
          
            &a = nums; for(int i=0; i
           
            i && r+1

16. 3Sum Closest

class Solution {public:    int threeSumClosest(vector
     
      & nums, int target) {        sort(nums.begin(), nums.end());        int n = nums.size();        int mind = INT_MAX, ans = 0;        vector
      
        &a = nums;        for(int i=0; i

18. 4Sum

class Solution {public:    vector
     
      
       > fourSum(vector
       
        & nums, int target) {        vector
        
          &a = nums;        sort(a.begin(), a.end());        vector
         
          
           > ans; int n = a.size(); if(n < 4) return ans; for(int i=0; i
           
            j && r+1