算法题之四数之和问题求解

算法题之四数之和问题求解

问题描述

思路分析

代码实现[思路图解可以参考直接博客三数之和问题]

链接地址:算法题之三数之和问题

public List<List<Integer>> fourSum(int[] nums, int target) { List<List<Integer>> res = new ArrayList<>(); //首先对该数组进行排序处理 Arrays.sort(nums); //首先对nums进行判断 if (nums == null || nums.length < 4) { return res; } //遍历排序以后的数组 for (int i = 0; i < nums.length; i++) { //(1)若当前nums[i]大于target值,则有nums[i]开始的四个数的和必然大于target;(2)或者下标i到数组尾部的元素个数小于4个 //注意:因为存在负数的情况,所以条件(1)不满足 if (nums.length - i < 4) { break;//直接退出for循环 } if (i > 0 && nums[i] == nums[i - 1]) { //i进行去重处理 continue; } //保持nums[i]不变,对后续的数组元素进行遍历 for (int j = i + 1; j < nums.length; j++) { //同样j进行去重处理 if (j > i + 1 && nums[j] == nums[j - 1]) { continue; } //分别定义左指针和右指针 int left = j + 1; int right = nums.length - 1; while (left < right) { int sum = nums[i] + nums[j] + nums[left] + nums[right]; if (sum == target) { res.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--; left++; right--; }else if (sum < target) { left++; }else if (sum > target) { right--; } } } } //for循环结束,res返回 return res; }