两数之和

  1. 两数之和的话需要遍历两次
  2. 条件是nums[i] + nums[j] == target

题目解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
package com.code.note.arrays;

import java.util.Arrays;

public class TwoSum {

    public int[] twoSum(int[] nums, int target) {
        int[] arr = new int[2];
        for (int i = 0; i < nums.length - 1; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) {
                    arr[0] = i;
                    arr[1] = j;
                    break;
                }
            }
        }

        return arr;
    }

    public static void main(String[] args) {
        TwoSum t = new TwoSum();
        int[] arr = t.twoSum(new int[]{2, 7, 11, 15}, 9);
        System.out.println(Arrays.toString(arr));
    }
}

三数之和

三数之和

  1. 因为leetcode测试用例比较大，使用三次遍历会有超时问题，所以我们需要使用排序 + 二分查找优化查询
  2. 其中寻找的第三个值为前两个相加值的负数
  3. 二分查找第三个值时候low位置的值应该是j+1，避免返回重复值
  4. 二分查找第三个值时候high位置需要避免最后一位出现多次问题，我这里是在第二个循环上限制 j<nums.length-1，避免出现在[-4,-1,0,1,1,2]中出现[-4，2，2]这种情况
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        quickSort(nums, 0, nums.length - 1);

        Set<List<Integer>> arr = new HashSet<>();
        for (int i = 0; i < nums.length - 1; i++) {
            for (int j = i + 1; j < nums.length-1; j++) {
                int target = -(nums[i] + nums[j]);
                int index = binarySearch(nums, target, j+1, nums.length - 1);
                if (index != -1) {
                    addNewElement(arr, nums[i], nums[j], nums[index]);
                }
            }
        }

        return new ArrayList<>(arr);
    }

    public static void quickSort(int[] nums, int left, int right) {

        if (left >= right) {
            return;
        }

        int pIndex = partition(nums, left, right);
        quickSort(nums, left, pIndex - 1);
        quickSort(nums, pIndex + 1, right);
    }

    private static int partition(int[] nums, int left, int right) {

        int pivot = left;
        int pIndex = pivot + 1;

        for (int i = pIndex; i <= right; i++) {
            if (nums[i] < nums[pivot]) {
                swap(nums, i, pIndex);
                pIndex++;
            }
        }
        swap(nums, pivot, pIndex - 1);

        return pIndex - 1;

    }

    private static void swap(int[] nums, int i, int j) {
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }

    public static int binarySearch(int[] arr, int target, int low, int high) {
        int l = low;
        int h = high;

        while (l <= h) {
            int mid = (h + l) / 2;
            if (arr[mid] > target) {
                h = mid - 1;

            } else if (arr[mid] < target) {
                l = mid + 1;
            } else {
                return mid;
            }

        }
        return -1;
    }

    private void addNewElement(Set<List<Integer>> arr, int num, int num1, int num2) {

        List<Integer> a = new ArrayList<>();
        a.add(num);
        a.add(num1);
        a.add(num2);
        arr.add(a);
    }
}