两数之和

题目

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

提示

给定 nums = [2, 7, 11, 15], target = 9

  • 因为 nums[0] + nums[1] = 2 + 7 = 9
  • 所以返回 [0, 1]

解答代码

public class Solution {

    /**
    * 第一版本
    *
    * @param nums
    * @param target
    * @return
    */
    public int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < nums.length; j++) {
                if (i == j) {
                    continue;
                }
                int temp = nums[i] + nums[j];
                if (target == temp) {
                    return new int[]{i, j};
                }
            }
        }
        throw new IllegalArgumentException("No two sum solution");
    }

    /**
    * 官方解法一
    *
    * @param nums
    * @param target
    * @return
    */
    public int[] twoSumtWO(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[j] == target - nums[i]) {
                    return new int[]{i, j};
                }
            }
        }
        throw new IllegalArgumentException("No two sum solution");
    }

    /**
    * 官方解法二
    * 时间复杂度:O(n)O(n),
    * 我们把包含有 nn 个元素的列表遍历两次。由于哈希表将查找时间缩短到 O(1)O(1) ,所以时间复杂度为 O(n)O(n)。
    * <p>
    * 空间复杂度:O(n)O(n),
    * 所需的额外空间取决于哈希表中存储的元素数量,该表中存储了 nn 个元素。
    *
    * @param nums
    * @param target
    * @return
    */
    public int[] twoSumThree(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], i);
        }
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (map.containsKey(complement) && map.get(complement) != i) {
                return new int[]{i, map.get(complement)};
            }
        }
        throw new IllegalArgumentException("No two sum solution");
    }

    /**
    * 官方解法三
    *
    * @param nums
    * @param target
    * @return
    */
    public int[] twoSumFou(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (map.containsKey(complement)) {
                return new int[]{map.get(complement), i};
            }
            map.put(nums[i], i);
        }
        throw new IllegalArgumentException("No two sum solution");
    }


    @Test
    public void testA() {
//        int[] nums = {1, 2, 3, 4};
//        int[] nums = {2, 2, 3, 4};
        int[] nums = {3,3};
//        int[] ints = twoSumtWO(nums, 4);
        int[] ints = twoSumThree(nums, 6);
//        int[] ints = twoSumFou(nums, 6);
        for (int anInt : ints) {
            System.out.println(anInt);
        }
    }

}

  转载请注明: 程序员小黑 两数之和

 本篇
两数之和 两数之和
题目给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。 提示给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nu
2019-12-12
下一篇 
MyBatis逆向工具使用方法 MyBatis逆向工具使用方法
POM文件导入相关Jar包 <?xml version="1.0" encoding="UTF-8"?> <project xmlns="http://maven.apac
2019-07-08
  目录