LeetCode——18. 四数之和

题目描述：

解题思路：

10月leetcode全是数字和的题，解题思路大概都差不多，就看怎么优化让复杂度更低，不然暴力的循环，只会TLE。这道题先排序，用双指针，省去一层循环，注意剪枝的条件，考虑的全面一点，也有利于优化算法运行的时间。 参考代码：

public List<List<Integer>> fourSum(int[] nums, int target){ List<List<Integer>> lists=new ArrayList<>(); if(nums==null||nums.length<4){ return lists; } Arrays.sort(nums); int len=nums.length; //每层循环判断与之前元素是否相同，如果相同继续下一层循环 for (int i = 0; i <len-3 ; i++) { if(i>0&&nums[i]==nums[i-1]){ continue; } //当前最小i连加起来都超过了题意，没有符合的 if(nums[i]+nums[i+1]+nums[i+2]+nums[i+3]>target){ break; } //当前i和最大的几个加起来都小于给的target，继续下一层循环 if(nums[i]+nums[len-3]+nums[len-2]+nums[len-1]<target){ continue; } for (int j = i+1; j <len-2 ; j++) { if(j>i+1&&nums[j]==nums[j-1]){ continue; } //这层循环里和上一层逻辑差不多，都是没有满足题意的 if (nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) { break; } //比题意小，继续下层循环 if(nums[i]+nums[j]+nums[len-2]+nums[len-1]<target){ continue; } //双指针省去一层循环 int left=j+1,right=len-1; while (left<right){ int sum=nums[i]+nums[j]+nums[left]+nums[right]; if(sum==target){ lists.add(Arrays.asList(nums[i],nums[j],nums[left],nums[right])); while (left<right&&nums[left]==nums[right]){ //去重 left++; } while (left<right&&nums[right]==nums[left]){ //去重 right--; } left++; right--; }else if(sum<target){ left++; } else { right--; } } } } return lists; }