两数之和-算法详细题解LeetCode

算法题：两数之和。

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

示例:

给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

import java.util.HashMap;

public class TwoSum {
    public static void main(String[] args) {
        int[] nums = {3, 3, 3};
        int target = 6;

        // int[] res = twoSum_Test1(nums, target); //调用解法一
        int[] res = twoSum_Test2(nums, target); //调用解法二

        System.out.println("数组下标是： " + res[0] + " " + res[1]);
        System.out.println(res.toString());
    }
//解法一：暴力解法
   /*
    思路：运用两次for循环遍历数组，将符合条件的下标存入结果数组。
    分析：时间复杂度O（n2），效率比较低。
    易错点：
            -第二次for循环注意初始值是i+1，而不是0。
            -返回数组存放的是下标，而不是数组里面的值。
    思考：
            -如果没有符合的值，此时如何处理返回值？默认返回[0，0]，还是异常处理
            -int[] res = twoSum(nums, target);这一语句里面res数组的长度大小由函数返回确定。
            -通过返回匿名对象来使代码更简洁高效（省略了数组的初始化和赋值）
    */

    public static int[] twoSum_Test1(int[] nums, int target) {
        //int[] res = new int[2];   //数组默认值初始化为0
        for (int i = 0; i < nums.length; i++) {
            int flag = target - nums[i];
            for (int i1 = i + 1; i1 < nums.length; i1++) {
                if (nums[i1] == flag) {
                    /*
                    res[0] = i;
                    res[1] = i1;
                    return res;
                    */
                    return new int[]{i, i1}; //使用匿名对象来使代码更简洁高效
                }
            }
        }

        throw new IllegalArgumentException("无结果产生");//抛出非法数据异常
        /*
        System.out.println("没有找到符合条件的值");
        return res;
         */
    }


    //解法二：哈希表法
    /*
    思路：使用哈希表来存储数组元素，利用哈希表快速查找的特性，将查找的时间复杂度从O（n）降到O(1)，本质是空间换时间。
    分析：时间复杂度O(n)，减少了查询时间，从而提高了效率
    易错点：HashMap常见静态方法使用错误
    思考：
         -HashMap<Key,Value>存在Key值唯一的特性，数组中的元素转移到哈希表中，后面添加的元素会把前面Key值相同的元素覆盖，所以，此时可能会疑惑若是数组存在相同值哈希表无法处理本问题。注意在用哈希表进行查询操作时，在遍历时用到的是数组，数组能够辅助记录被覆盖的元素，来解决本问题。
         -但是哈希表法存在局限性。若有多个相同的数值，且该数满足条件，如nums [3,3,3]，target=6，此时合理答案为[0,1]，但输出结果为[0,2]，缘由不难想象。
     */
    
    public static int[] twoSum_Test2(int[] nums, int target) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], i);             //数组中的值作为Key，下标作为Value
        }
        for (int i = 0; i < nums.length; i++) {
            int flag = target - nums[i];
            if (map.containsKey(flag) && map.get(flag) != i) {//与判断的后者是用来排除自身元素
                return new int[]{i, map.get(flag)};
            }
        }
        throw new IllegalArgumentException("无结果产生");
    }

    //哈希表法的优化
    /*
    思路：每次从数组取出一个元素，然后判断哈希表中是否存在该元素，判断结束之后，把当前元素存放到哈希表中，只需一次迭代。
    思考：
         -本优化方法做的改进是不要一次性把数组存放到哈希表中，而是边查询边存放，其实仔细想想，这种方法和现实生活中的实际场景十分类似。
     */
    //代码和解法二差别不多，不再单独书写。
}

两数之和-算法详细题解LeetCode

算法题：两数之和。

相关推荐