欢迎来到尧图网

客户服务 关于我们

您的位置:首页 > 房产 > 建筑 > 15.三数之和(LeetCode)java

15.三数之和(LeetCode)java

2025/4/30 6:17:35 来源:https://blog.csdn.net/m0_74779497/article/details/147423358  浏览:    关键词:15.三数之和(LeetCode)java

个人理解:

1.使用双指针做法,首先对数组进行排序

        第一重for循环控制第一个数,对数组进行遍历。双指针初始化为left=i+1, rigth=nums.length-1。然后使用while循环移动双指针寻找合适的数。因为返回的是数,不是下标,数不能重复,所以需要去重。对于第一重for循环,当i大于0的时候,要判断是否和前一个数相同,如果相同,则跳过当前数进行去重。

2.双指针移动

当nums[i]+nums[left]+nums[right]>0时,说明大了,最右边的right指针需要减减操作(right--)

当nums[i]+nums[left]+nums[right]<0时,说明小了,最左边的left指针需要加加操作(left++)

当nums[i]+nums[left]+nums[right]==0时,开始收集结果。

3.结果收集

收集完结果后,要移动双指针,这时候也要对双指针进行去重。

指针去重操作:

        对于left指针,如果nums[left]==nums[left+1],说明下一位重复,那么left要持续++;

        对于right指针,如果nums[right]==nums[right-1],说明下一位重复,那么right要持续--;

以上两种情况都要主要前提条件,即left<right

无论以上两种情况是否执行,都需要left++和right--更新双指针。

最后将结果收集 res.add(Arrays.asList(nums[i],nums[left],nums[right]))

res是List<List<Integer>>类型,Arrays.asList()是将一组元素变为List

class Solution {public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> res=new ArrayList<>();Arrays.sort(nums);  //先排序for(int i =0;i<nums.length;i++){if(nums[i]>0)   //如果第一个元素大于0,直接跳出循环break ;if(i>0&&nums[i]==nums[i-1])  //对于第一个元素,去重continue;int left=i+1;   // 双指针int right=nums.length-1;// 指针开始移动while(left<right){if(nums[i]+nums[left]+nums[right]>0){  // 太大了,右指针移动right--;}else if(nums[i]+nums[left]+nums[right]<0){  // 太小了,左指针移动left++;}else{//收集结果res.add(Arrays.asList(nums[i],nums[left],nums[right]));// 开始对指针去重,也就是对第二、第三个元素去重while(left<right&&nums[right]==nums[right-1])right--;while(left<right&&nums[left]==nums[left+1])left++;// 移动双指针left++;right--;}}}return res; }
}

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

热搜词