LeetCode 1099. 小于 K 的两数之和

Categories:

题目描述
思路分析
1. 解法一：排序 + 双指针（推荐）
相似题目

题目描述

✅ 1099. 小于 K 的两数之和

思路分析

解法一：排序 + 双指针（推荐）

核心思路：

先对数组排序，使用左右指针夹逼。

若当前和小于 K，尝试更新答案并左指针右移。

若当前和大于等于 K，右指针左移降低和。

复杂度分析：

时间复杂度：O(n log n)，其中 n 表示数组长度。

空间复杂度：O(1)（不计排序栈空间）。

import java.util.Arrays;

class Solution {
    public int twoSumLessThanK(int[] nums, int k) {
        Arrays.sort(nums);

        int left = 0;
        int right = nums.length - 1;
        int best = -1;

        while (left < right) {
            int sum = nums[left] + nums[right];
            if (sum < k) {
                if (sum > best) {
                    best = sum;
                }
                left++;
            } else {
                right--;
            }
        }

        return best;
    }
}

import "sort"

func twoSumLessThanK(nums []int, k int) int {
	sort.Ints(nums)

	left, right := 0, len(nums)-1
	best := -1

	for left < right {
		sum := nums[left] + nums[right]
		if sum < k {
			if sum > best {
				best = sum
			}
			left++
		} else {
			right--
		}
	}

	return best
}

相似题目

题目	难度	考察点
167. 两数之和 II - 输入有序数组	中等	双指针
15. 三数之和	中等	排序、双指针
1099. 小于 K 的两数之和	简单	排序、双指针
259. 较小的三数之和	中等	排序、双指针
16. 最接近的三数之和	中等	排序、双指针

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/34118172