只买域名不建网站,聊城做网站的公司渠道,网站开发与托管协议,wordpress导航菜单跳转文章目录 15. 三数之和题干#xff1a;算法原理#xff1a;1、排序 暴力枚举 利用set 去重2、排序 双指针 代码#xff1a; 18. 18. 四数之和题干#xff1a;算法原理#xff1a;1、排序 暴力枚举 利用set 去重2、排序 双指针 代码#xff1a; 15. 三数之和 原题链… 文章目录 15. 三数之和题干算法原理1、排序 暴力枚举 利用set 去重2、排序 双指针 代码 18. 18. 四数之和题干算法原理1、排序 暴力枚举 利用set 去重2、排序 双指针 代码 15. 三数之和 原题链接
题干
存在一个三元组,满足 i ! j、i ! k 且 j ! k nums[i] nums[j] nums[k] 0
算法原理
1、排序 暴力枚举 利用set 去重
这个方法就是先循环用几个 for 循环暴力枚举然后放到 HashSet 中去重 但是这个方法时间复杂度很高达到了O(N3)
2、排序 双指针
1排序 这里进行排序是为了从前向后遍历的时候可以更好的用双指针进行操作 2固定一个数 a 这个 a 必须要大于等于 0因为题目要求三数相加等于 0
3在该数后面的区间内利用“双指针算法”快速找到两个数的和等于 -a 即可
4处理细节问题 不要漏任何一个组合 在 left 和 right 向中间走的时候找到一个数等于固定的数的负数不能停下继续缩小区间寻找下一个 去重 由于题目要求不能返回相同的数组所以要求去重 这样就可以找到一种结果之后left 和 right 指针要跳过重复元素 当使用完一次双指正算法之后也要跳过重复元素 但要注意避免越界
代码 public ListListInteger threeSum(int[] nums) {ListListInteger ret new ArrayList();//1.排序Arrays.sort(nums);int n nums.length;//2.利用双指针for (int i 0; i n;) {int left i 1;int right n - 1;int target -nums[i];if (nums[i] 0) {break;}while (left right) {int sum nums[left] nums[right];if (sum target) {left;}else if (sum target) {right--;}else {ret.add(new ArrayListInteger(Arrays.asList(nums[i],nums[left],nums[right])));//缩小区间继续寻找left;right--;while (left right nums[left] nums[left-1]) {left;}while (left right nums[right] nums[right1]) {right--;}}}i;while (i n nums[i] nums[i-1]) {i;}}return ret;}18. 18. 四数之和 题干
这道题跟上面的三数之和非常相似因此下面的解题思路也是非常相似
nums[a] nums[b] nums[c] nums[d] target
算法原理
1、排序 暴力枚举 利用set 去重
这个算法依然是超时的我们主要看第二种
2、排序 双指针
1排序
2在 a 后面的区间内利用“三数之和”找到三个数和上面题的方法一样使这三个数的和等于 target - a
3处理细节问题
不漏去重
代码
public ListListInteger fourSum(int[] nums, int target) {ListListInteger ret new ArrayList();int n nums.length;//1.排序Arrays.sort(nums);//2.双指针for (int i 0; i n;) {long t1 (long)target - nums[i];for (int j i 1; j n;) {long t2 t1 - nums[j];int left j 1;int right n - 1;while (left right) {int sum nums[left] nums[right];if (sum t2) {right--;}else if (sum t2) {left;}else {ret.add(Arrays.asList(nums[i],nums[j],nums[left],nums[right]));left;right--;while (left right nums[left] nums[left-1]) {left;}while (left right nums[right] nums[right1]) {right--;}}}j;while (j n nums[j] nums[j-1]) {j;}}i;while (i n nums[i] nums[i-1]) {i;}}return ret;}
