网站开发用什么语言最多,广东省住房和城乡建设局官网,移动终端网站建设,新网 网站建立18. 四数之和
解题思路
外围的四数之和#xff08;fourSumTarget 方法#xff09;#xff1a; 首先对输入数组nums进行排序#xff0c;这样可以方便后面进行双指针搜索#xff0c;同时也有助于去除重复的元组。遍历排序好的数组#xff0c;固定第一个数nums[i]然后对剩…18. 四数之和
解题思路
外围的四数之和fourSumTarget 方法 首先对输入数组nums进行排序这样可以方便后面进行双指针搜索同时也有助于去除重复的元组。遍历排序好的数组固定第一个数nums[i]然后对剩余的部分进行三数之和的搜索。每次找到三数之和的结果(temp)后将固定的数nums[i]添加到每个三元组中转换成一个四元组并加入最终结果res中。在每次循环的最后移动指针i跳过相同的元素以防止四元组重复。 中间层的三数之和threeSum 方法 从指定的start位置开始遍历固定第一个数nums[i]然后在剩余数组中寻找两个数其和为target - nums[i]。通过调用twoSumTarget方法来找出所有满足条件的两数之和的组合temp。将每个找到的组合temp转换成三元组将固定的数nums[i]添加进去。同样的移动指针i跳过重复元素以防重复的三元组。 最内层的两数之和twoSumTarget 方法 使用双指针方法来找出所有和为给定target的两个数这里的target是由threeSum方法传递下来的目标和。通过左右指针left和right在排序数组中向中间搜索当找到两数之和等于目标时记录这一对数到结果列表。与前两个方法相同对左右指针分别向内移动以跳过重复的元素防止结果集中出现重复的组合。
class Solution {// 转换为三数之和 在转换为两数之和ListListInteger res new ArrayList();public ListListInteger fourSum(int[] nums, int target){return fourSumTarget(nums,(long)target);}public ListListInteger fourSumTarget(int[] nums, long target) {// 首先对数组进行排序Arrays.sort(nums);int n nums.length;for(int i 0; i n; i){ListListInteger temp threeSum(nums,i1,target - (long)nums[i]);// 添加元素 成为三元组for(ListInteger t: temp){t.add(nums[i]);res.add(t);}// 去除第一个重复元素while(i n - 1 nums[i] nums[i1]){i;}}return res;}public ListListInteger threeSum(int[] nums, int start,long target){int n nums.length;ListListInteger result new ArrayList();for(int i start; i n; i){// 满足条件的temp 不止一个ListListInteger temp twoSumTarget(nums,i1,target - (long)nums[i]);// 添加元素 成为三元组for(ListInteger t: temp){t.add(nums[i]);result.add(t);}// 去除第一个重复元素while(i n - 1 nums[i] nums[i1]){i;}}return result;}public ListListInteger twoSumTarget(int[] nums, int start,long target){int n nums.length;ListListInteger result new ArrayList();int left start;int right n - 1;long t target;while(left right){long sum (long)nums[left] (long)nums[right];long l nums[left];long r nums[right];if(sum t){ListInteger a new ArrayList();a.add(nums[left]);a.add(nums[right]);result.add(a);// 去除重复的元素while(left right nums[left] l){left;}// 去除重复元素while(left right nums[right] r){right--;}}else if(sum t){while(left right nums[left] l){left;}}else if(sum t){while(left right nums[right] r){right--;}}}return result;}
}
