题目

输入一个递增排序的数组和一个数字s,在数组中查找两个数,使得它们的和正好是s。如果有多对数字的和等于s,则输出任意一对即可。

思路

利用双指针法,这里有个条件是已经有序。
使用双指针,一个指针指向元素较小的值,一个指针指向元素较大的值。指向较小元素的指针从头向尾遍历,指向较大元素的指针从尾向头遍历。

如果两个指针指向元素的和 sum == target,那么这两个元素即为所求。
如果 sum > target,移动较大的元素,使 sum 变小一些;
如果 sum < target,移动较小的元素,使 sum 变大一些。

code

fun twoSum(nums: IntArray, target: Int): IntArray {
        if(nums.isEmpty()){
            return intArrayOf()
        }
        var i =0
        var j = nums.size-1
        var sum = 0
        while(i&lt;j){
            sum = nums[i]+nums[j]
            if(sum == target){
                return intArrayOf(nums[i],nums[j])
            }else if(sum &lt;target){
                i++
            }else if(sum&gt;target){
                j--
            }
        }
        return intArrayOf()
    }

发表评论

电子邮件地址不会被公开。 必填项已用*标注