使用三种算法来解决Two-Sum问题

https://www.bilibili.com/video/BV12V411a7xm

题目

给定一个数组，给定一个数字n，求数组中是否存在两个数相加和是n

比如数组[2，4，6，7，1]

第一种算法：

public class Test1 {

    public boolean twoSum(int[] arr, int n) {

        for (int i = 0; i < arr.length; i++) {

            for (int j = 0; j < i; j++) {

                if (arr[j] + arr[i] == n) {

                    System.out.printf("arr[%d]=%d，arr[%d]=%d \n", j, arr[j], i, arr[i]);

                    return true;

                }

            }

        }

        return false;

    }

    public static void main(String[] args) {
        int[] arr = {2,4,6,7,1};
        Test1 test1 = new Test1();
        test1.twoSum(arr, 10);
    }

}

思路：

从第i个数开始，依次尝试i之前的每一个数和i的和是否等于目标数。

时间复杂度是 O(n²/2)

第二种算法

import java.util.HashMap;
import java.util.Map;

public class Test2 {

    public boolean twoSum(int[] arr, int n) {

        Map<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < arr.length; i++) {

            if (map.containsKey(n - arr[i])) {

                System.out.printf("arr[%d]=%d，arr[%d]=%d \n", map.get(n - arr[i]), n - arr[i], i, arr[i]);

                return true;

            }

            map.put(arr[i], i);

        }

        return false;

    }

    public static void main(String[] args) {
        int[] arr = {2,4,6,7,1};
        Test2 test = new Test2();
        test.twoSum(arr, 10);
    }
}

思路：

遍历数组，判断 目标数和当前数的差 是否存在于已经遍历过的元素中，不存在就将当前数放入已经遍历过的数的集合。

时间复杂度是 O(n)，但还有O(n)的空间复杂度，需要字典来存放已遍历数。