題目
給你一個下標從?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;}
}