南充网站建设价格,网站开发全科班,wordpress更改站点,wordpress 数据库 开发此问题属于nsum问题#xff0c;题目链接#xff1a;力扣
要求在数组中找到不重复的三元组#xff0c;三个数加起来为0#xff0c;且每个下标只能用一次。而且需要返回所有这样的不重复数组。
1. 排序 双指针
1. 「不重复」的本质是什么#xff1f;我们保持三重循环的大…此问题属于nsum问题题目链接力扣
要求在数组中找到不重复的三元组三个数加起来为0且每个下标只能用一次。而且需要返回所有这样的不重复数组。
1. 排序 双指针
1. 「不重复」的本质是什么我们保持三重循环的大框架不变只需要保证
第二重循环枚举到的元素不小于当前第一重循环枚举到的元素第三重循环枚举到的元素不小于当前第二重循环枚举到的元素。
也就是说我们枚举的三元组 (a, b, c) 满足 a ≤ b ≤ c保证了只有 (a, b, c) 这个顺序会被枚举到而(b, a, c)、(c, b, a) 等等这些不会这样就减少了重复。要实现这一点我们可以将数组中的元素从小到大进行排序随后使用普通的三重循环就可以满足上面的要求。
2. 对于每一重循环而言相邻两次枚举的元素不能相同否则也会造成重复但是对于初学者来讲为了简化题目可以先不考虑重复结果的处理 2. 不考虑重复
我们可以先考虑不处理重复结果的情况代码如下注释全整版 public ListListInteger threeSum(int[] nums) {int n nums.length;Arrays.sort(nums); // 排序是前提ListListInteger ans new ArrayList();// 枚举 afor (int a 0; a n; a) {int c n - 1; // 将c初始指向数组最后一位int target -nums[a]; // 这是b和c的目标和for (int b a 1; b n; b) { // b 暂时固定按部就班的递增while (b c nums[b] nums[c] target){c--;}// 如果b和c的和太大c就左移if (c b) break; // a b 确定下c已经退无可退了所以break// 后续就算是b再递增这个总和也是太大没有合适的c了if (nums[b] nums[c] target){ListInteger list new ArrayList();list.add(nums[a]);list.add(nums[b]);list.add(nums[c]);ans.add(list);}}}return ans;}
其实不加处理重复的话代码很简单哈哈 3.加上对重复的判定
后续对于重复答案的处理就是要求a不重复b不重复在代码中分别加上这两段验证即可
1. 对于a
if (a 0 nums[a] nums[a - 1]) continue;
2. 对于b
if (b a 1 nums[b] nums[b - 1]) continue;
由以上思路得出的本题目的完整版代码如下注释完整版
class Solution {public ListListInteger threeSum(int[] nums) {int n nums.length;Arrays.sort(nums);ListListInteger res new ArrayList();for (int a 0; a n; a) {if (a 0 nums[a] nums[a - 1]) continue; // 每个数只能当一次aint c n - 1;int target -nums[a];// 枚举bfor (int b a 1; b n; b) { // b从a后一个开始if (b a 1 nums[b] nums[b - 1]) continue; // b a1代表// 比如说 0 1 1这个数组如果a指向0b指向第二个1那就没必要了// 因为每个数字只能当一次bwhile (b c nums[b] nums[c] target) {--c;}// 如果指针重合随着 b 后续的增加// 就不会有满足 abc0 并且 bc 的 c 了可以退出循环if (b c) {break;}if (nums[b] nums[c] target) {ListInteger list new ArrayListInteger();list.add(nums[a]);list.add(nums[b]);list.add(nums[c]);res.add(list);}}}return res;}
}
时间复杂度在n 3000的数据范围内可以满足要求
