当前位置：首页 > article >正文

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

article 2024/11/14 20:28:38

🙉专栏推荐: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;
    }
}