LeetCode集锦（一） - two sum

布满荆棘的人生 2022-10-01 08:56 5阅读 0赞

# LeetCode集锦（一） - two sum #

## 问题 ##

Given an array of integers, return indices of the two numbers such that they add up to a specific target. 
    
     You may assume that each input would have exactly one solution, and you may not use the same element twice. 
    
     Example: 
    
    
    Given nums = [2, 7, 11, 15], target = 9,
    
    Because nums[0] + nums[1] = 2 + 7 = 9,
    return [0, 1].
    
    复制代码

### 翻译: ###

> 给定一个整数数组，返回两个数字的索引，使它们加起来等于一个特定的目标。
> 
> 您可以假设每个输入都只有一个解决方案，并且不能两次使用相同的元素。
> 
> 给定数组:\[2, 7, 11, 15\] ,两数和为:9
> 
> 因为按顺序而言，2+7等于9，所以选择2和7对应的下标，0，1构成新数组。返回结果为\[0,1\]

--------------------

## 解题思路 ##

本题字面含义其实是求和，找寻两个数字的和为目标值，然后输出该两个数字的下标值。

换一个角度而言，我们这边有一个最终结果值--目标值，和一系列待选值--数组，如果我们在待选值中选择一个值，由目标值减去改值，就是另外需要寻找的值。这样我们就拿到全部需要的结果，需要做的只是从待选值中，查找那个差值。

## 解题方法 ##

1.  第一种解体方法，按照我们的思路来编辑，代码如下
    
        for (int i = 0; i < nums.length; i++) {
                int differ = target - nums[i];
        
                for (int m = i + 1; m < nums.length; m++) {
                    if (differ == nums[m]) {
                        return new int[]{i, m};
                    }
                }
            }
            return new int[]{};
        复制代码
    
    **时间复杂度**: 该方案用了两层嵌套循环，第一层循环度为n，第二层循环度也是n-m,所以f(n)=n\*(n-m)=n^2-mn;所以O(f(n))=O(n^2),即T(n)=O(n^2)
    
    **空间复杂度**: 该方案并没有使用额外度空间去存储，所以空间复杂度还是O(1);
2.  第二种解题方法，是延伸出来，既然我们要寻找另外一个值，是否可以用map这类数据结构来方便查询呢？代码如下:
    
        //先转化为hashmap
            Map<Integer, Integer> map = new HashMap<>(nums.length);
            for (int i = 0; i < nums.length; i++) {
                map.put(nums[i], i);
            }
        
            for (int i = 0; i < nums.length; i++) {
                Integer integer = map.get(target - nums[i]);
                //如果是本身，就跳过
                if (integer != null && integer!=i) {
                    return new int[]{i, integer};
                }
            }
            return new int[]{};
        复制代码
    
    **时间复杂度**: 该方案用了单层循环，两次单层循环,所以f(n)=n+n=2n;所以O(f(n))=O(2n)=O(n),即T(n)=O(n)
    
    **空间复杂度**: 该方案使用了HashMap去存储数值和索引的关系，所以是原来数组的近似2倍（这边不考虑因为数据结构而导致的开销),即为2n,所以总共的空间复杂度为O(f(n))=O(3n)=O(n),所以空间复杂度还是O(n);
3.  第三种解题方案是针对与第二种解题优化的，第二种方案是直接把数组转化为map，所以这部分的空间开销是固定，如果我们可以一边读取，一边储存，那么是否可以更加简单呢？因为9-2=7，相对的9-7=2。所以按照这种思路，出现了第三种解题方案,代码如下:
    
        Map<Integer, Integer> map = new HashMap<>(nums.length);
        for (int i = 0; i < nums.length; i++) {
           int differ = target - nums[i];
           Integer result = map.get(differ);
           if (null != result) {
              return new int[]{result,i };
           }
           map.put(nums[i], i);
        }
        return new int[]{};
        复制代码

## 总结 ##

本题的大致解法如上所诉，但是可以更改的方式很多，如果输入的数组出现重复的情况，那么方法2是一个致命的错误解法，因为会把它覆盖，所以个人觉得，方法三是相对较优的一种解法。

转载于:https://juejin.im/post/5cd03b575188252526406cb8