java算法题 : 数组相关问题

package com.wjk.test; import java.util.ArrayList; import java.util.Arrays; import java.util.List; /** * @author : RobertWei * time: 2021/9/9 17:06 * description:三数之和答案 */ public class Answer { public static void main(String[] args) { int[] nums = {0, 2, 5, 3, -2, -3}; List<List<Integer>> threeSum = threeSum(nums); System.out.println("threeSum = " + threeSum); } public static List<List<Integer>> threeSum(int[] nums) {// 总时间复杂度：O(n^2) List<List<Integer>> ans = new ArrayList<>(); if (nums == null || nums.length <= 2) { return ans; } // O(nlogn) Arrays.sort(nums); // O(n^2) for (int i = 0; i < nums.length - 2; i++) { if (nums[i] > 0) { // 第一个数大于 0，后面的数都比它大，肯定不成立了 break; } if (i > 0 && nums[i] == nums[i - 1]) { continue; // 去掉重复情况 } int target = -nums[i]; int left = i + 1, right = nums.length - 1; while (left < right) { if (nums[left] + nums[right] == target) { ans.add(new ArrayList<>(Arrays.asList(nums[i], nums[left], nums[right]))); // 现在要增加 left，减小 right，但是不能重复， // 比如: [-2, -1, -1, -1, 3, 3, 3], i = 0, left = 1, right = 6, [-2, -1, 3] 的答案加入后，需要排除重复的 -1 和 3 // 首先无论如何先要进行加减操作 left++; right--; while (left < right && nums[left] == nums[left - 1]) { left++; } while (left < right && nums[right] == nums[right + 1]) { right--; } } else if (nums[left] + nums[right] < target) { left++; } else { // nums[left] + nums[right] > target right--; } } } return ans; } }