力扣(LeetCode)LCR 179. 查找总价格为目标值的两个商品(Java)

🙉专栏推荐:Java入门知识🙉

🐹今日诗词:西山白雪三城戍，南浦清江万里桥🐹

---

⛳️点赞 ☀️收藏⭐️关注💬卑微小博主🙏

⛳️点赞 ☀️收藏⭐️关注💬卑微小博主🙏

---

目录

 题目描述

题目解析

正常思路(暴力解法)

双指针算法

代码

复杂度分析

美图分享

---

 题目描述

链接: LCR 179. 查找总价格为目标值的两个商品

购物车内的商品价格按照升序记录于数组 price。请在购物车中找到两个商品的价格总和刚好是 target。若存在多种情况，返回任一结果即可。

示例 1：

输入：price = [3, 9, 12, 15], target = 18
输出：[3,15] 或者 [15,3]

示例 2：

输入：price = [8, 21, 27, 34, 52, 66], target = 61
输出：[27,34] 或者 [34,27]

提示：

• 1 <= price.length <= 10^5
• 1 <= price[i] <= 10^6
• 1 <= target <= 2*10^6

题目解析

正常思路(暴力解法)

正常思路： 两个for循环，计算两数和的所有可能情况， 然后与target比较, 但是这样会超时

双指针算法

双指针算法： 这个数组是升序数组（这点非常重要），

定义两个指针，分别在数组左右两端,left, right

情况1： price[left] + price[right] > target

大于目标值说明右边指针大了，应该right--才能接近目标值

情况2: price[left] + price[right] < target

小于目标值，说明左指针小了，应该left++才能接近目标值

情况3: price[left] + price[right] == target

等于目标值， 说明找到了，left和right对应的值就是答案

代码

循环终止条件: left++， right--， 当他们相遇说明没找到, 因此循环条件是 while (left < right)

class Solution {
    public int[] twoSum(int[] price, int target) {
        // 定义左右指针
        int left = 0;
        int right = price.length - 1;

        // 数组存储答案
        int[] arr = new int[2];
        while (left < right) {
            if (price[left] + price[right] > target) {
                right--;
            } else if(price[left] + price[right] < target) {
                left++;
            } else {
                arr[0] = price[left];
                arr[1] = price[right];
                // 找到一种情况就可以跳出循环了
                break;
            }
        }
        return arr;
    }
}

复杂度分析

美图分享

✨🎆谢谢你的阅读和耐心！祝愿你在编程的道路上取得更多的成功与喜悦！"🎆✨🎄

⭐️点赞收藏加关注，学习知识不迷路⭐️

🎉✔️💪🎉✔️💪🎉✔️💪🎉✔️💪🎉

👍😏⛳️点赞☀️收藏⭐️关注😏👍

👍😏⛳️点赞☀️收藏⭐️关注😏👍

👍😏⛳️点赞☀️收藏⭐️关注😏👍

🙆‍♂️🙆‍♂️🙆‍♂️🙆‍♂️🙆‍♂️🙆‍♂️🙆‍♂️🙆‍♂️🙆‍♂️🙆‍♂️🙆‍♂️🙆‍♂️🙆‍♂️

原文地址：https://blog.csdn.net/qq_34471880/article/details/143700088

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！