Day 18

第18题:

给定一个包含 n 个整数的数组 nums 和一个目标值 target,判断 nums 中是否存在四个元素 a,b,c 和 d ,使得 a + b + c + d 的值与 target 相等?找出所有满足条件且不重复的四元组。

注意:答案中不可以包含重复的四元组。来源:力扣(LeetCode)、

1、求和为target的四个数的组合,和三数之和类似,也可以用双指针的方法,将前两个指针固定,另外两个指针分别移动遍历;

  先将数组排序,使之成为升序数组;

  设四个指针为a,b,c,d,a和b指向第一个和第二个数组元素,c指向第三个数组元素,d指向数组最后一个元素;

  由于数组升序,所以当a和b指针移动时,只可能遇见和自己相同的或者比自己大的,此时需要避免遇见和自己相同的;

  这样将前两个值固定,再利用双指针分别遍历处另两个值,可以得出不重复的四元组集合。

  

  /*获取当前最小值,如果最小值比目标值大,说明后面越来越大的值根本没戏,忽略*/
  int min=nums[k]+nums[i]+nums[j]+nums[j+1];
  if(min>target){
    continue;
  }
  /*获取当前最大值,如果最大值比目标值小,说明后面越来越小的值根本没戏,忽略*/
  int max=nums[k]+nums[i]+nums[h]+nums[h-1];
  if(max<target){
    continue;
  }

  在其中可加入判断此时的四数组合的最小值和最大值来减少一些多余的遍历。

原文地址:https://www.cnblogs.com/liang-yi-/p/13277030.html