LeetCode 18

概述

• https://leetcode-cn.com/problems/4sum/
• 给你一个数组和一个目标值target，判断数组中是否能找到四个不同位置的值相加等于target
• 答案中不包含重复的集合

思路

• 和之前[3Sum](LeetCode 15.md)基本相同，只是需要四个数字

• 指针数：2个活动指针+2个固定移动指针

  class Solution {
  public:
      vector<vector<int>> fourSum(vector<int>& nums, int target) {
          vector<vector<int>> result;
          sort(nums.begin(),nums.end());
          int L=nums.size();
          for(int i=0;i<L;i++){
              //if(nums[i]>target)  continue;	这个剪枝是错误的
              if(i>0&&nums[i]==nums[i-1]) continue;	//相同的去重操作
              for(int j=i+1;j<L;j++){			//两个固定指针，两重循环
                  if(j>i+1&&nums[j]==nums[j-1]) continue;		//注意一下第二重循环的去重条件
                  int left=j+1;
                  int right=L-1;
                  while(right>left){
                      if((long long )nums[i]+nums[j]+nums[left]+nums[right]>target)	//这里的类型v
                          right--;
                      else if((long long )nums[i]+nums[j]+nums[left]+nums[right]<target)
                          left++;
                      else{
                          result.push_back(vector<int>{nums[i], nums[j], nums[left],nums[right]});
                          while(nums[right]==nums[right-1]&&right>left) right--;
                          while(nums[left]==nums[left+1]&&right>left) left++;
                          right--;
                          left++;
                      }
                  }
              }
          }
          return result;
      }
  };

  ​

​