使用三种算法来解决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)的空间复杂度，需要字典来存放已遍历数。

第三种算法

public class Test3 {

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

        bubbleSort(arr);

        System.out.print(arr[0]);

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

            System.out.printf(", %d", arr[i]);

        }

        System.out.println();

        //排序结束

        int left = 0;
        int right = arr.length - 1;

        while (left < right) {

            int ret = arr[left] + arr[right];

            if (ret == n) {

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

                return true;

            } else if (ret < n) {

                left++;

            } else if (ret > n) {

                right--;

            }

        }

        return false;

    }

    public static void bubbleSort(int[] arr) {

        if (arr == null || arr.length < 2) {
            return;
        }

        for (int e = arr.length - 1; e > 0; e--) {// 0 ~ e

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

                if (arr[i] > arr[i + 1]) {

                    swap(arr, i, i + 1);
                }

            }//end for

        }//end for

    }//end bubbleSort

    public static void swap(int[] arr, int i, int j) {
        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[i] ^ arr[j];
        arr[i] = arr[i] ^ arr[j];
    }

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

}

思路：

首先得让数组有序——必须从左到右是从小到大，然后设置左右两个指针，让两个指针向中间移动，因为数组有序，所以左右两个指针肯定一个是从小到大移动、另一个从大到小进行移动，

左右相加小于目标数时右移小到大的左指针，左右相加大于目标数时左移大到小的右指针，直至两指针重合。

时间复杂度是O(n)，空间复杂度是O(1)（left、right），但是需要对数组进行预先排序。