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

在每一次困境中都要寻找胜利的希望。

前言

明天要出差，接下来又只能断更了。还是继续一边学习kotlin一边练习使用。

题目

参考LCR 179. 查找总价格为目标值的两个商品。

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

解题思路

• 双指针：明显克使用双指针，因为左边指针会使两个指针的和变大，右边指针会使两个指针的和变小，根据与目标值的大小比较决定移动哪边的指针。

双指针 解法

class Solution {
    fun twoSum(price: IntArray, target: Int): IntArray {
        // 因为price有序，可使用双指针
        val n = price.size
        var left = 0; var right = n-1
        while(left < right) {
            if(price[left] + price[right] == target)
                return intArrayOf(price[left], price[right]) 
            else if(price[left] + price[right] < target) left ++
            else right --
        }
        return IntArray(2)
    }
}

复杂度分析

• 时间复杂度：O(n)，n为数组长度。
• 空间复杂度：O(1)。

2023.10.11