联盟网站制作,河南建设168工程网官方网站,营业执照解除异常收费多少钱,手机版cad简单制图软件给定一个包含 n 个整数的数组 nums#xff0c;判断 nums 中是否存在三个元素 a#xff0c;b#xff0c;c #xff0c;使得 a b c 0 #xff1f;找出所有满足条件且不重复的三元组。
注意#xff1a;答案中不可以包含重复的三元组。
例如, 给定数组 nums [-1, 0, 1,…给定一个包含 n 个整数的数组 nums判断 nums 中是否存在三个元素 abc 使得 a b c 0 找出所有满足条件且不重复的三元组。
注意答案中不可以包含重复的三元组。
例如, 给定数组 nums [-1, 0, 1, 2, -1, -4]满足要求的三元组集合为
[[-1, 0, 1],[-1, -1, 2]
]import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;public class Solution {public static void main(String[] args) {int[] nums { -1, 0, 1, 2, -1, -4 };ListListInteger threeSum threeSum(nums);for (ListInteger list : threeSum) {for (Integer sum : list) {System.out.print(sum );}System.out.println();}}private static ListListInteger threeSum(int[] nums) {// 双指针思想先对nums排序三个数拆成12形式第一个数nums[k]一定小于等于0后两个数通过设置两个指针 i,j 分别指向数组两端// 如果两指针所指向数nums[i]和nums[j]的和sub大于-nums[k]j指针前移找一个更小的数如果两指针所指向数的和小于target// i指针后移找一个更大点的数如果相同则返回即可。 ListListInteger res new ArrayList();Arrays.sort(nums); // -4, -1, -1, 0, 1, 2for (int k 0; k nums.length; k) {if (nums[k] 0 || (k 0 nums[k] nums[k - 1])) {continue; // 最小的数大于0不可能再组成结果0了 或者 返回的第一个数相等去重}int i k 1, j nums.length - 1;while (i j) {int sub nums[i] nums[j];if (sub -nums[k]) {ListInteger list new ArrayList();list.add(nums[k]);list.add(nums[i]);list.add(nums[j]);res.add(list); // 添加结果while (i j nums[i] nums[i 1]) { // 第二个数相等去重i;}while (i j nums[j] nums[j 1]) { // 第三个数相等去重j--;}i;j--;} else if (sub -nums[k]) {j--; // 三个数的和大于0第三个数减小点} else {i; // 三个数的和小于0第二个数增大点}}}return res;}}
