两数之和

[PisecesPeng]

两数之和

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

你可以假设每种输入只会对应一个答案. 但是, 你不能重复利用这个数组中同样的元素.

示例:

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

题目地址: https://leetcode-cn.com/problems/two-sum/

[PisecesPeng]

解题思路

• 题目思路比较简单, 无论'暴力枚举'还是'哈希表'来做都可以得出答案,
• 以上两种题解就不考虑(留给官方题解), 我打算使用'二分查找'去解决.
• 思路就直接写在代码注释里了.

代码

private static List<Integer> func(int[] nums, int target) {
    List<Integer> result = new ArrayList<>();  // 存放结果

    int[] sortNums = Arrays.copyOf(nums, nums.length);
    Arrays.sort(sortNums);  // 排序(为下文的二分法查找做准备)
    // 确认最小值是否大于target
    if (sortNums[0] > target) return result;

    int length = sortNums.length;
    Integer v1 = null, v2 = null;  // 存放符合题意的两个值
    // 二分法查找
    for (int i = 0; i < sortNums.length; i++) {
        // 先确定如果有两个符合题意的数字, 其数值应该是多少
        int leftNum = sortNums[i];
        int rightNum = target - leftNum;
        // 设置二分法查找的index范围
        int leftIndex = i + 1;
        int rightIndex = length - 1;
        while (leftIndex < rightIndex) {
            int midIndex = (leftIndex + rightIndex) / 2;
            // 如果找到符合题意的数组, 直接设置v1、v2的值, 并跳出循环
            if (sortNums[midIndex] == rightNum) {
                v1 = leftNum;
                v2 = rightNum;
                break;
            }
            if (sortNums[midIndex] > rightNum) {
                rightIndex = midIndex;
            } else {
                leftIndex = midIndex + 1;
            }
        }
        // 若v1、v2不为null, 则直接跳出循环
        if (!Objects.isNull(v1) && !Objects.isNull(v2)) break;
    }

    // 再根据v1、v2的值, 遍历nums[]取得下标
    if (!Objects.isNull(v1) && !Objects.isNull(v2)) {
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == v1 || nums[i] == v2) {
                if (result.size() >= 2) {
                    break;
                } else if (result.size() > 0) {
                    if (nums[i] != (target - nums[result.get(0)])) continue;
                    else result.add(i);
                } else {
                    result.add(i);
                }
            }
        }
    }
    return result;
}

[PisecesPeng]

LeetCode题解

解题思路

• 暴力枚举, target减去当前值获得目标值, 通过遍历数组来寻找是否存在目标值.

代码

public static int[] func(int[] nums, int target) {
    int n = nums.length;
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            if (nums[i] + nums[j] == target) {
                return new int[]{i, j};
            }
        }
    }
    return new int[0];
}

[PisecesPeng]

LeetCode题解

解题思路

• 使用哈希表去保存所有'值'与'下标',
• 遍历, 通过targer减去当前值获得的目标值作为key, 直接去哈希表中查找.

代码

public static int[] func(int[] nums, int target) {
    Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>();
    for (int i = 0; i < nums.length; ++i) {
        if (hashtable.containsKey(target - nums[i])) {
            return new int[]{hashtable.get(target - nums[i]), i};
        }
        hashtable.put(nums[i], i);
    }
    return new int[0];
}