57Ⅰ.和为s的两个数字

参考链接

剑指offer_在线编程_牛客网

剑指 Offer 57. 和为s的两个数字-跟着帅地玩转校招，刷爆各类算法题帅地玩Offer

LCR 179. 查找总价格为目标值的两个商品 - 力扣（LeetCode）

个人尝试（❌错误）

尝试使用一个HashMap存储数组元素方便找寻target -= price[i]后是否有满足target == price[i]，

并且使用Queue存储数组元素中相加可能target的元素，

事实证明，思路与正确解法存在很大偏差，把题解复杂化了，并且该思路只能求相邻元素的组合，没办法实现跨越组合，即 a, b, c 只能组合 a+b / b+c / a+b+c ... 没办法求 a+c

class Solution {
    public int[] twoSum(int[] price, int target) {
        Queue<Integer> queue = new ArrayDeque<>();
        Map<Integer, Boolean> map = new HashMap<>();
        for (int i : price) {
            map.put(i, true);
        }
        for (int i = 0; i < price.length; i++) {
            if (target >= price[i]) {
                if (target == price[i] && map.get(price[i]) == true) {
                    queue.offer(price[i]);
                    int[] arr = new int[queue.size()];
                    int j = 0;
                    while (!queue.isEmpty()) {
                        arr[j++] = queue.poll();
                    }
                    return arr;
                }
                target -= price[i];
                queue.offer(price[i]);
                map.put(price[i], false);
            } else {
                if (!queue.isEmpty()) {
                    while (!queue.isEmpty() && target < price[i]) {
                        int tmp = queue.poll();
                        map.put(tmp, true);
                        target += tmp;
                    }
                    i--;
                }
            }
        }
        return new int[0];
    }
}

优秀题解

class Solution {
    // price 为有序数组
    public int[] twoSum(int[] price, int target) {
        // 双指针
        int i = 0, j = price.length - 1;
        while(i < j) {
            int s = price[i] + price[j];
            if(s < target) i++;
            else if(s > target) j--;
            else return new int[] { price[i], price[j] };
        }
        return new int[0];
    }
}

作者：Krahets
链接：https://leetcode.cn/problems/he-wei-sde-liang-ge-shu-zi-lcof/solutions/164083/mian-shi-ti-57-he-wei-s-de-liang-ge-shu-zi-shuang-/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。