＜leetcode＞力扣-两数之和

青旅半醒 2023-10-08 22:40 63阅读 0赞

## 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、具体解法**（本体用了五种解法，，其实核心应该算两种，一种是暴力遍历，一种是[哈希表][Link 1]，不过两种解法都可以结合二分法用两个指针从两端同时进行遍历来提高速度package day1\_两数之和;  
  
import java.util.HashMap;  
import java.util.Map;  
  
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;  
\}  
  
  
  
\}

### 2.[二分法][Link 2] ###

二分法，可以理解为 a + b = c 现在我们可以确定 a 和 c，要想找到b就只需要 c - a 即可，然后就可以从数组的两头开始找起

public class TwoNumberSum {
        public static void main(String[] args) {
            TwoSumTest2 twoSumTest = new TwoSumTest2();
            int[] num = {2, 5, 11, 15, 6, 8, 7};
            System.out.println(Arrays.toString(twoSumTest.twoSum(num, 9)));
    		// 最终返回结果[0, 6]
        }
    }
    
    /**
     * 二分法
     */
    class TwoSumTest2{
        public int[] twoSum(int[] nums, int target) {
            /**
             * 假如只有两个数，那么就直接返回
             */
            int[] result = {0, 1};
            if (nums.length <= 2) {
                return result;
            }
    
            /**
             * 数组里的数大于两个数
             */
            for (int i = 0; i < nums.length - 1; i++) {
                /**
                 * [2, 7, 11, 15]
                 * 先锁定一个数，也就是第一个 2
                 */
                result[0] = i;
                /**
                 * 这里可以理解为：a + b = c 那么a和c确定了就可以确定b 所以x就是那个b
                 */
                int x = target - nums[i];
                /**
                 * 接下来就是开始找 b
                 * 这里巧妙的运用了二分法，从两头开始找起如果符合就直接返回
                 * (从两头往中间找)
                 */
                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;
        }
    }

### 3.[哈希表][Link 1] ###

哈希表实际上采用的就是containsKey()这个方法来找key，可以说是先将数组存到哈希表中，然后在通过找b来找到对应的结果

public class TwoNumberSum {
        public static void main(String[] args) {
            TwoSumTest1 twoSumTest = new TwoSumTest1();
            int[] num = {2, 5, 11, 15, 6, 8, 7};
            System.out.println(Arrays.toString(twoSumTest.twoSum(num, 9)));
    		// 最终返回结果[0, 6]
        }
    }
    
    /**
     * 哈希表法
     */
    class TwoSumTest3{
        public int[] twoSum(int[] nums, int target) {
            /**
             * [2, 5, 11, 15, 7] 9
             * 还是 a + b = c
             * 先定义一个hashMap 利用hashMap中的containKey方法来确定b
             */
            Map<Integer, Integer> hashMap = new HashMap<>();
            for (int i = 0; i < nums.length; i++) {
                /**
                 * 第一次进入循环hashMap是空的，什么也没有，然后put第一个数
                 * 第二次进循环 得到9 - 5 = 4 然后和hashMap里的key进行比较
                 * 此时hashMap{(2,0)}
                 * 第三次进循环 得到9 - 11 = -2 然后和hashMap里的key进行比较
                 * 此时hashMap{(2,0),(5,1)}
                 * 第四次进循环 得到9 - 15 = -6 然后和hashMap里的key进行比较
                 * 此时hashMap{(2,0),(5,1),(11,2)}
                 * 第五次进循环 得到9 - 7 = 2 然后和hashMap里的key进行比较
                 */
                if (hashMap.containsKey(target - nums[i])) {
                    return new int[]{hashMap.get(target - nums[i]), i};
                }
                hashMap.put(nums[i], i);
            }
            return new int[]{};
        }

*  **暴力拆解**
 *  暴力拆解很好理解，两个for循环，拿第一个数与其他进行比较，最终得到正解返回
    
        public class TwoNumberSum {
            public static void main(String[] args) {
                TwoSumTest1 twoSumTest = new TwoSumTest1();
                int[] num = {2, 5, 11, 15, 6, 8, 7};
                System.out.println(Arrays.toString(twoSumTest.twoSum(num, 9)));
        		// 最终返回结果[0, 6]
            }
        }
        
        /**
         * 暴力拆解
         */
        class TwoSumTest1 {
            public int[] twoSum(int[] nums, int target) {
                for (int i = 0; i < nums.length; i++) {
                    for (int j = i + 1; j < nums.length; j++) {
                        if (nums[i] + nums[j] == target) {
                            return new int[]{i, j};
                        }
                    }
                }
                return new int[]{};
            }
        }

*  
 *  这种求和的题目，有数组的，可以想到暴力解决
 *  这种题目的目的，其实是找一个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循环对应的四分法
 *  有序：对撞指针或者二分法，无序：哈希表（这个收获还没太清晰，以后遇到类似的再去看看）

[Link 1]: https://so.csdn.net/so/search?q=%E5%93%88%E5%B8%8C%E8%A1%A8&spm=1001.2101.3001.7020
[Link 2]: https://so.csdn.net/so/search?q=%E4%BA%8C%E5%88%86%E6%B3%95&spm=1001.2101.3001.7020