LeetCode18

LeetCode18

注意!其中nums数值的范围,四个加一起会导致INT溢出,long类型则是64位的整数,因此不会导致溢出,这也是本题难点之一!

大佬解法(拿捏offer的解法)

经过反复的代码比对和Debug,发现大佬解法的速度之快体现在足足7个if语句的剪枝,其中包括了2个关键性的去重的if语句以及2个关键性的k,h去重while语句!!!

class Solution {public List<List<Integer>> fourSum(int[] nums, int target) {List<List<Integer>> ans=new ArrayList<>();int i=0,j=0,k=0,n=nums.length,h=n-1;Arrays.sort(nums);for(;i<n-3;++i){j=i+1;if((nums[i]>0&&target<0)||(nums[i]>=Integer.MAX_VALUE/4)){//剪枝1return ans;}     if(i>0&&nums[i]==nums[i-1]){//i的去重,剪枝2continue;}if((long)nums[i]+nums[i+1]+nums[i+2]+nums[i+3]>target){//剪枝3break;}  if((long)nums[i]+nums[n-3]+nums[n-2]+nums[n-1]<target){//剪枝4continue;}for(;j<n-2;++j){k=j+1;h=n-1;if(j>i+1&&nums[j]==nums[j-1]){// j的去重,剪枝5continue;}if((long)nums[i]+nums[j]+nums[j+1]+nums[j+2]>target){//剪枝6break;}if((long)nums[i]+nums[j]+nums[n-1]+nums[n-2]<target){//剪枝7continue;}for(;k<h;){long sum=0;sum=(long)nums[i]+nums[j]+nums[k]+nums[h];if(sum==target){List<Integer> res=Arrays.asList(nums[i],nums[j],nums[k],nums[h]);ans.add(res);// h=n-1;// k++;while(k<h&&nums[k]==nums[k+1]){k++;}//k的去重k++;while(k<h&&nums[h]==nums[h-1]){h--;}//h的去重--h;}else if(sum>target){h--;}else if(sum<target){k++;}}}}return ans;}
}

暴力解法(面试必挂,只能回家斗地主的解法)

根据三数之和的经验和力抠提示的测试用例通过了,md真的比较难

class Solution {public List<List<Integer>> fourSum(int[] nums, int target) {List<List<Integer>> ans=new LinkedList<>();int i=0,j=0,k=0,n=nums.length,h=n-1;Arrays.sort(nums);for(;i<n-3;++i){j=i+1;if(nums[i]>=Integer.MAX_VALUE/4){return ans;}       for(;j<n-2;++j){k=j+1;h=n-1;for(;k<h;){int sum=0;sum=nums[i]+nums[j]+nums[k]+nums[h];if(sum>target){h--;}else if(sum<target){k++;}else {List<Integer> res=new LinkedList<>();res.add(nums[i]);res.add(nums[j]);res.add(nums[k]);res.add(nums[h]);if(!ans.contains(res))//速度瓶颈在这里,卡在17ms的时间ans.add(res);h=n-1;k++;while(k>=1&&k<n&&nums[k]==nums[k-1]){k++;}while(h>=0&&h+1<n&&nums[h]==nums[h+1]){h--;}}}}}return ans;}
}