15. 3Sum

一、题目

　　1、审题

　　　　

 

　　2、分析：

　　　　给出一个数字型数组，求任意三个数组中数字和为0的所有组合。

 

二、解答

　　1、分析：

　　　　a、将数组 nums 排序，遍历数组中元素；

　　　　b、遍历下标为 i 的元素时，取 low 指针指向下标为 i + 1 的元素， high 指向数组最后一个元素下标；

　　　　c、循环判断 当 low < high 时，

　　　　　　若  nums[i] + nums[low] + nums[high] = 0 , 则为一组符合的组合；　　

　　　　　　　　同时，low 和 high 继续移动，若 nums[low] = nums[low+1]，则 low++;

　　　　　　　　若 nums[high] = nums[high -1] ， 则 high--；

　　　　　　若 nums[i] + nums[low] + nums[high] > 0， 则 high--；

　　　　　　若 nums[i] + nums[low] + nums[high] < 0， 则 low++；

public class Solution {public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> list = new ArrayList<List<Integer>>();Arrays.sort(nums);int sum = 0;for(int i = 0; i < nums.length -2; i++) {

　　　　　　　if(nums[i] > 0) break;
if(i == 0 || (i > 0 && nums[i] != nums[i-1])) { // 第一个已经比过，排除相等的两连续元素int low = i + 1;int high = nums.length - 1;sum = -nums[i];

　　　　　　　　　　while(low < high) { // 拎出 nums[i]， low 与high 相夹if(nums[low] + nums[high] == sum) {
　　　　　　　　　　　　　　list.add(Arrays.asList(nums[i], nums[low], nums[high]));while(low < high && nums[low] == nums[low + 1]) low++;while(low < high && nums[high] == nums[high - 1]) high--;low++;high--;} else if (nums[low] + nums[high] < sum) {low++;} else {high--;}}}}return list;} }

 

转载于:https://www.cnblogs.com/skillking/p/9409352.html

总结

以上是生活随笔为你收集整理的15. 3Sum的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。