LeetCode之路——3Sum

2019-11-06 06:15:51

字体：大中小

来源：转载

供稿：网友

题目要求：给一个整数数组，找出数组中三个数的和为0，不能有重复的结果。思路：先将数组排序，扫描数组，找出和为0-nums[i]的，过程中跳过相同的结果。贴上代码：

package leetcode;import java.util.ArrayList;import java.util.Arrays;import java.util.List;public class ThereSum15 { public static void main(String[] args) { int[] nums = {-1, 0, 1, 2, -1, -4}; Solution_TS ts = new Solution_TS(); System.out.PRintln(ts.threeSum(nums)); }}class Solution_TS { public List<List<Integer>> threeSum(int[] nums) { List<List<Integer>> res = new ArrayList<>(); Arrays.sort(nums);//排序 for (int i = 0; i + 2 < nums.length; i++) { if (i > 0 && nums[i] == nums[i - 1]) { // 跳过相同的 continue; } int j = i + 1, k = nums.length - 1;//从前后扫描 int target = 0-nums[i];//求两个数的和为0-nums[i] while (j < k) { if (nums[j] + nums[k] == target) { res.add(Arrays.asList(nums[i], nums[j], nums[k])); j++; k--; while (j < k && nums[j] == nums[j - 1]) j++; // 跳过相同的 while (j < k && nums[k] == nums[k + 1]) k--; // 跳过相同的 } else if (nums[j] + nums[k] > target) { k--; } else { j++; } } } return res; }}

总结：分析问题，将问题分解成小的问题域，再求解！

上一篇：十六进制字符串转换成字符字符串

下一篇：并查集详解