刚开始做网站布局很吃力 怎么办,毛绒玩具东莞网站建设,企业网站建设要注意哪方面,沧州网络运营中心电话其实这道题就是求2数之和#xff0c;和3数之和的衍生吧#xff0c;核心算法还是双指针#xff1b; 暴力解法就不再说了#xff1a;排序暴力set去重#xff1b;
直接上#xff1a;排序双指针去重 大致思路如上图#xff0c;如果要详细算法过程#xff0c;可以就看看两数… 其实这道题就是求2数之和和3数之和的衍生吧核心算法还是双指针 暴力解法就不再说了排序暴力set去重
直接上排序双指针去重 大致思路如上图如果要详细算法过程可以就看看两数之和和三数之和。 代码实现
class Solution {public static ListListInteger fourSum(int[] nums, int target) {Arrays.sort(nums);ListListInteger lists new ArrayList();int nnums.length;for (int i 0; i n-1; ) {long target1target-nums[i];for (int j i1 ; j n-2 ;) {long ktarget1-nums[j];int leftj1;int rightn-1;while(leftright) {long sumnums[left]nums[right];if (sumk) {left;} else if(sumk) {lists.add(new ArrayList(Arrays.asList(nums[i],nums[j],nums[left],nums[right])));left;right--;while(leftrightnums[right]nums[right1]) {right--;}while (leftrightnums[left]nums[left-1]) {left;}} else {right--;}}j;while(jnnums[j]nums[j-1]) {j;}}i;while(innums[i]nums[i-1]) {i;}}return lists;}
}官方实现
class Solution
{public ListListInteger fourSum(int[] nums, int target){ListListInteger ret new ArrayList();// 1. 排序Arrays.sort(nums);// 2. 利⽤双指针解决问题int n nums.length;for(int i 0; i n; ) // 固定数 a{// 三数之和for(int j i 1; j n; ) // 固定数 b{// 双指针int left j 1, right n - 1;long aim (long)target - nums[i] - nums[j];while(left right){int sum nums[left] nums[right];if(sum aim) right--;else if(sum aim) left;else{ret.add(Arrays.asList(nums[i], nums[j], nums[left],nums[right--]));// 去重⼀while(left right nums[left] nums[left - 1])left;while(left right nums[right] nums[right 1])right--;}}// 去重⼆j;while(j n nums[j] nums[j - 1]) j;}// 去重三i;while(i n nums[i] nums[i - 1]) i;}return ret;}
}这里最难的是去重和越界细节的去除一定要画图和调试代码找出问题。
