ETH官方钱包

前往
大廳
主題

LeetCode - 2824. Count Pairs Whose Sum is Less than Target 解題心得

Not In My Back Yard | 2024-10-30 12:00:11 | 巴幣 2 | 人氣 51

題目連結:


題目意譯:
給定一個索引值從 0 開始數且長度 n 的整數陣列 nums 以及一整數 target。回傳數對 (i, j) 的數量,其中 0 ≦ i < j < n 且 nums[i] + nums[j] < target。

限制:
1 ≦ nums.length == n ≦ 50
-50 ≦ nums[i], target ≦ 50



範例測資:
範例 1:
輸入: nums = [-1,1,2,3,1], target = 2
輸出: 3
解釋: 有 3 個索引值數對滿足條件:
- (0, 1) 因為 0 < 1 且 nums[0] + nums[1] = 0 < target
- (0, 2) 因為 0 < 2 且 nums[0] + nums[2] = 1 < target
- (0, 4) 因為 0 < 4 且 nums[0] + nums[4] = 0 < target
注意到 (0, 3) 不被計入其中,因為 nums[0] + nums[3] 並沒有嚴格小於 target。

範例 2:
輸入: nums = [-6,2,5,-2,-7,-1,3], target = -2
輸出: 10
解釋: 有 10 個索引值數對滿足條件:
- (0, 1) 因為 0 < 1 且 nums[0] + nums[1] = -4 < target
- (0, 3) 因為 0 < 3 且 nums[0] + nums[3] = -8 < target
- (0, 4) 因為 0 < 4 且 nums[0] + nums[4] = -13 < target
- (0, 5) 因為 0 < 5 且 nums[0] + nums[5] = -7 < target
- (0, 6) 因為 0 < 6 且 nums[0] + nums[6] = -3 < target
- (1, 4) 因為 1 < 4 且 nums[1] + nums[4] = -5 < target
- (3, 4) 因為 3 < 4 且 nums[3] + nums[4] = -9 < target
- (3, 5) 因為 3 < 5 且 nums[3] + nums[5] = -3 < target
- (4, 5) 因為 4 < 5 且 nums[4] + nums[5] = -8 < target
- (4, 6) 因為 4 < 6 且 nums[4] + nums[6] = -4 < target


解題思維:
因為 nums 的長度最多只有 50 個元素,因此直接用一個時間複雜度 O(n ^ 2) 的方式來解即可——也就是說,直接窮舉出所有可能的數對並檢查和統計即可。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作