1、两数之和

1、问题描述

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那两个整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

2、示例

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]
示例 3：

输入：nums = [3,3], target = 6
输出：[0,1]

3、提示

• 2 <= nums.length <= 104
• -109 <= nums[i] <= 109*
• -109 <= target <= 109
• 只会存在一个有效答案

4、进阶

你可以想出一个时间复杂度小于 O(n2) 的算法吗？

5、具体解法（本体用了五种解法，，其实核心应该算两种，一种是暴力遍历，一种是哈希表，不过两种解法都可以结合二分法用两个指针从两端同时进行遍历来提高速度）

package day1_两数之和;

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

//2022年3月21日10:58:28
//直接这个类没法执行啊，在leetcode上可以运行提交，但是本地的话，这个代码没法运行
public class Solution {
    //public static void main(String[] args) {//为什么不用写这个，直接就是执行这个类,写了这个也不行，因为会提示非法的开始，没有调用程序的部分，不过我应该会写了

       /*
        //解法一，用暴力枚举的方式,注意边界
        public int[] twoSum (int[] nums, int target){//首先方法是数组类型的，因为要返回的是数组类型。两个参数也是对应的写好，符合写程序的思路
            int n = nums.length;
            for (int i = 0; i < nums.length - 1; i++) {//i是外层循环，而且只需要判断到倒数第二个数即可，因为最后一个数由内层循环提供
                for (int j = i + 1; j < nums.length; j++) {//j是内层循环，从i+1开始，且需要判断到最后一个数
                    if (nums[i] + nums[j] == target) {
                        return new int[]{i, j};//当符合条件的时候就输出一个数组，里面的内容是此时的i和j，也就是下标
                                               //这个数组连名字都没有也可以？
                    }
                }
            }
            return new int[0];//当for循环都跳出了，还是没有，就返回一个空数组
        }

     */


    /*
       //解法二：用HashMap的方式
        public int[] twoSum(int[] nums, int target) {
            Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>();//创建一个HashMap集合，Map是键值对的形式，而HashMap是键值唯一
            for (int i = 0; i < nums.length; ++i) {
                if (hashtable.containsKey(target - nums[i])) {//判断每一个值x对应的target-x是不是存在，为什么是containsKey而不是value
                                                              //因为这个map的键值对种是下标是值，键反而是数组中是数值
                    return new int[]{hashtable.get(target - nums[i]), i};//存在就返回两个下标，其中的target-x下标可以用HashMap的get方法获得
                }
                hashtable.put(nums[i], i);//并不是先将所有数据都放进HashMap，而是从第一个数先开始判断，然后再将这个数放进Map中，可以避免自己跟自己匹配
            }                             //而且要注意键值对，谁是键，谁是值
            return new int[0];
        }

      */

    
    /*
    //解法三、双指针，二分大法
    //这其实是一道搜索题，固定一个数后，就是如何找到另外一个数（target - [i]）。
    //因为是数组，要利用随机访问的能力，因此内部loop可以用双指针从两头往中间找，这样可以节省一半的时间，整体时间复杂度会到O(nlogn)，仍要注意边界.

    public int[] twoSum(int[] nums, int target) {
        int[] result = {0, 1};
        if (nums.length <= 2) {
            return result;//这里我觉得不去return这个，而是return new int[0];比较合适
        }

        for (int i = 0; i < nums.length - 1; i++) {
            result[0] = i;
            int x = target - nums[i];
            for (int j = i + 1, k = nums.length - 1; j <= k; j++, k--) {//对内部循环做双指针寻找，但我感觉本质还是                                                                           遍历呢，但执行时间减了很多
                if (nums[j] == x) {
                    result[1] = j;
                    return result;
                }
                if (nums[k] == x) {
                    result[1] = k;
                    return result;
                }
            }//你看其本质就是循环的时候不是一个个去看，而是两个两个去看，但还是全看了
        }

        return result;
    }

     */


    /*
    //解法四：内外都用双指针，四分大法
    //其实主loop也可以采用二分法，用双指针从两头往中间遍历，这样又可以节省一半的时间。
    //还可以做剪支，如果主loop的双指针之和恰好是target，那就直接返回，剪支在分析效率的时候可能帮助不大，但在真实的运行时，能大大提高效率。
    //在不借助额外的数据结构的前提下，这是最优解，从运行结果来看，时间是0，严格来说是O(n/2logn)。
    public int[] twoSum(int[] nums, int target) {
        int[] result = {0, 1};
        if (nums.length <= 2) {
            return result;
        }

        for (int i = 0, j = nums.length - 1; i < j; i++, j--) {
            if (nums[i] + nums[j] == target) {
                // Lucky
                result[0] = i;
                result[1] = j;
                return result;
            }

            // should be in [i+1, j-1], find them with double pointers.
            int x = target - nums[i];
            int y = target - nums[j];//这两个的作用就是后面写起来可以清晰一点，把一个长的用一个符号来代替
            for (int k = i + 1, m = j - 1; k <= m; k++, m--) {
                result[0] = i;
                if (nums[k] == x) {
                    result[1] = k;
                    return result;
                } else if (nums[m] == x) {
                    result[1] = m;
                    return result;
                }

                result[1] = j;
                if (nums[k] == y) {
                    result[0] = k;
                    return result;
                } else if (nums[m] == y) {
                    result[0] = m;
                    return result;
                }
            }
        }

        return result;
    }

     */

    
    //解法五：二分加Map
    //其实一开始没想到用Map，因为以往做ACM的时候，一般来说不让直接使用标准库里的东西，这本是一个搜索，前面的四分法能满足要求，额外再实现一个Map，不太划算。
    //注意，题目中说返回结果不要求有一定的顺序，这就暗示了，可以使用Map来做内层的搜索，外层仍要遍历，内层用Map来搜索，整体效率会达到O(n)。
    //同时，受四分大法启发，外层主loop，其实仍可以用二分大法，这样时间复杂度又提高到O(n/2)。
    

    public int[] twoSum(int[] nums, int target) {
        int[] result = {0, 1};
        if (nums.length <= 2) {
            return result;
        }

        Map<Integer, Integer> valueToIndex = new HashMap<>();
        for (int i = 0, j = nums.length - 1; i <= j; i++, j--) {
            if (nums[i] + nums[j] == target) {
                //这种情况是第一个和最后一个恰好就是
                result[0] = i;
                result[1] = j;
                break;
            }
            int x = target - nums[i];
            if (valueToIndex.containsKey(x)) {
                result[0] = i;
                result[1] = valueToIndex.get(x);
                break;
            }
            x = target - nums[j];//这个比解法四还要省了一个变量的空间
            if (valueToIndex.containsKey(x)) {
                result[0] = j;
                result[1] = valueToIndex.get(x);
                break;
            }

            valueToIndex.put(nums[i], i);
            valueToIndex.put(nums[j], j);
        }

        return result;
    }



}

6、收获

• 这种求和的题目，有数组的，可以想到暴力解决
• 这种题目的目的，其实是找一个x并判断对应的target-x是否存在，这种理解题目的思路是我从没有过的，要学习
• 正是通过上面的那种理解，可以发现暴力法的问题在于寻找的过程是遍历全部，时间复杂度高，所以采用创建哈希表的方式，这种方式可以将两层for循环的O(N2)降低到O（N），原理是将所有数组元素先放进哈希表，这样是n个数据，O（N），而查的过程，不用遍历去找，哈希表是可以直接根据键值对进行定位的，所以整体的查找过程是O（N）的时间复杂度，但是多以哈希表的存储空间，所以是用空间换时间，空间复杂度由O（1）变为了O(N)。这种用空间换时间的思路要学会。
• 对于HashMap和containsKey()和get()有了更深入的理解，注意谁是键谁是值，这个是在存储的时候确定了的
• 对于return也有了新认识，需要返回多个数值的时候，可以使用数组来进行，而且return new int[]{里面是数组的内容}，直接就可以返回{内容}，不需要给数组起一个名字的。
• 写程序的思路：输入输出类型，循环边界，然后才是具体的方法使用
• 学习到的解题方法：暴力遍历，哈希表，二分法，双层for循环对应的四分法
• 有序：对撞指针或者二分法，无序：哈希表（这个收获还没太清晰，以后遇到类似的再去看看）
• 发现一道题的解法太多了，还有没收录进来的排序加数据封装加折半查找这样的方法可以以后再看