首页 > 代码库 > LeetCode关于数组中求和的题型
LeetCode关于数组中求和的题型
15. 3Sum：三数之和为0的组合
Note: The solution set must not contain duplicate triplets.
For example, given array S = [-1, 0, 1, 2, -1, -4],A solution set is:[ [-1, 0, 1], [-1, -1, 2]]
思路：循环法，先给数组排序->[-4,-1,-1,0,1,2],其中i,j,k三数的下标，i先为最左边的一个数，则i<n-3,此时可以根据求两数之和的方法来进行求解；
对一个有序的数组求两数之和为定值，最简单的方法为j,k分别为数组的两端，主键向中间靠拢；
具体代码如下：
import java.util.*;public class Solution { public List<List<Integer>> threeSum(int[] nums) { List<List<Integer>> lists = new ArrayList<>(); if(nums==null||nums.length==0) return lists; Arrays.sort(nums); int n = nums.length; int i=0; while(i<=n-3){ int j=i+1; int k = n-1; while(j<k){ if(nums[i]+nums[j]+nums[k]==0){ ArrayList<Integer> list = new ArrayList<Integer>(); list.add(nums[i]); list.add(nums[j]); list.add(nums[k]); lists.add(list); while(j<k&&nums[j]==nums[j+1]) j++; while(k>j&&nums[k]==nums[k-1]) k--; j++; k--; }else if(nums[i]+nums[j]+nums[k]<0){ j++; }else{ k--; } } while(i<n-1&&nums[i]==nums[i+1]) i++; i++; } return lists; }}
LeetCode关于数组中求和的题型
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。