题目
给你一个下标从 0 开始长度为
n的整数数组nums和一个整数target，请你返回满足0 <= i < j < n且nums[i] + nums[j] < target的下标对(i, j)的数目。
解题思路
- 对数组进行排序，可以利用List自带的sort函数传递比较规则(代码中的是倒序，也可以直接传null为默认的顺序排序)
- 通过两层循环进行遍历，第二层循环当出现符合条件的则剩余元素都符合，可以跳出当前循环减少消耗；
代码展示
class Solution { public int countPairs(List<Integer> nums, int target) { nums.sort((a, b) -> b - a); int sum = 0; int n = nums.size(); for (int i = 0; i < n; i++){ int temp = nums.get(i); for (int j = i + 1; j < n; j++){ if(temp + nums.get(j) < target){ sum += n - j; break; } } } return sum; } }
