《LeetCode力扣练习》代码随想录——哈希表（四数之和---Java）

《LeetCode力扣练习》代码随想录——哈希表（四数之和—Java）

刷题思路来源于 代码随想录

18. 四数之和

• 排序双指针

  class Solution {
      public List<List<Integer>> fourSum(int[] nums, int target) {
  
          List<List<Integer>> result=new ArrayList<>();
  
          if(nums.length<4){
              return result;
          }
  
          if(nums.length==4&&(long)nums[0]+nums[1]+nums[2]+nums[3]==target){
              result.add(Arrays.asList(nums[0],nums[1],nums[2],nums[3]));
              return result;
          }
  
          Arrays.sort(nums);
  
          for(int i=0;i<nums.length;i++){
  
              if(target>0&&nums[i]>target){
                  return result;
              }
  
              if(i>0&&nums[i]==nums[i-1]){
                  continue;
              }
  
              for(int j=i+1;j<nums.length;j++){
  
                  if(target>0&&nums[i]+nums[j]>target){
                      break;
                  }
  
                  if(j>i+1&&nums[j]==nums[j-1]){
                      continue;
                  }
  
                  int left=j+1;
                  int right=nums.length-1;
  
                  while(left<right){
  
                      long temp=(long) nums[i]+nums[j]+nums[left]+nums[right];
  
                      if(temp>target){
                          right--;
                      }else if(temp<target){
                          left++;
                      }else{
  
                          result.add(Arrays.asList(nums[i],nums[j],nums[left],nums[right]));
                          while(left<right&&nums[left]==nums[left+1]){
                              left++;
                          }
  
                          left++;
  
                          while(left<right&&nums[right]==nums[right-1]){
                              right--;
                          }
  
                          right--;
  
                      }
  
                  }
  
              }
  
          }
  
          return result;
  
      }
  }