LeetCode 259. 较小的三数之和

Categories:

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

题目描述

✅ 259. 较小的三数之和

思路分析

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

核心思路：

对数组排序，固定第一个数 i。

使用左右指针统计满足 nums[i] + nums[l] + nums[r] < target 的数量。

当和小于 target，l 与 r 之间所有组合均满足条件，直接累加。

复杂度分析：

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

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

import java.util.Arrays;

class Solution {
    public int threeSumSmaller(int[] nums, int target) {
        Arrays.sort(nums);
        int n = nums.length;
        int count = 0;

        for (int i = 0; i < n - 2; i++) {
            int left = i + 1;
            int right = n - 1;

            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum < target) {
                    count += right - left;
                    left++;
                } else {
                    right--;
                }
            }
        }

        return count;
    }
}

import "sort"

func threeSumSmaller(nums []int, target int) int {
	sort.Ints(nums)
	count := 0

	for i := 0; i < len(nums)-2; i++ {
		left, right := i+1, len(nums)-1
		for left < right {
			sum := nums[i] + nums[left] + nums[right]
			if sum < target {
				count += right - left
				left++
			} else {
				right--
			}
		}
	}

	return count
}

相似题目

题目	难度	考察点
15. 三数之和	中等	排序、双指针
16. 最接近的三数之和	中等	排序、双指针
259. 较小的三数之和	中等	排序、双指针
611. 有效三角形的个数	中等	排序、双指针
1099. 小于 K 的两数之和	简单	排序、双指针

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/71677953