🚀 算法題 🚀

🌲 算法刷題專欄 | 面試必備算法 | 面試高頻算法 🍀
🌲 越難的東西,越要努力堅持，因為它具有很高的價值，算法就是這樣?
🌲 作者簡介：碩風和煒，CSDN-Java領域新星創作者🏆，保研|國家獎學金|高中學習JAVA|大學完善JAVA開發技術棧|面試刷題|面經八股文|經驗分享|好用的網站工具分享💎💎💎
🌲 恭喜你發現一枚寶藏博主,趕快收入囊中吧🌻
🌲 人生如棋，我愿為卒，行動雖慢，可誰曾見我后退一步？🎯🎯

🚀 算法題 🚀

🚩 題目鏈接

• 2824. 統計和小于目標的下標對數目

? 題目描述

給你一個下標從 0 開始長度為 n 的整數數組 nums 和一個整數 target ，請你返回滿足 0 <= i < j < n 且 nums[i] + nums[j] < target 的下標對 (i, j) 的數目。

示例 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

提示：

1 <= nums.length == n <= 50
-50 <= nums[i], target <= 50

🌟 求解思路&實現代碼&運行結果

---

? 模擬

🥦 求解思路

1. 通過題目的要求，以及給定的數據量，直接暴力枚舉即可。
2. 具體實現代碼如下：

🥦 實現代碼

class Solution {public int countPairs(List<Integer> nums, int target) {int n=nums.size();int cnt=0;for(int i=0;i<n;i++){for(int j=i+1;j<n;j++){if(nums.get(i)+nums.get(j)<target) cnt++;}}return cnt;}
}

🥦 運行結果

? 二分

🥦 求解思路

1. 題目的順序對于最終的結果并沒有影響，所以，我們可以先對集合排序，然后遍歷每一個元素v，找到小于target-v最右側的元素位置。
2. 收集答案的過程中，需要注意的是，如果二分沒有找到對應的下標位置，還是之前位置的下標，此時最終結果不更新，相反，則需要更新。
3. 具體實現代碼如下：

🥦 實現代碼

class Solution {public int countPairs(List<Integer> nums, int target) {int n=nums.size();int cnt=0;Collections.sort(nums);for(int i=0;i<n;i++){int left=i-1,right=n;while(left+1<right){int mid=left+right>>1;if(nums.get(mid)<target-nums.get(i)){left=mid;}else{right=mid;}}if(left!=i-1) cnt+=(left-i);}return cnt;}
}

🥦 運行結果

---

💬 共勉

最后，我想和大家分享一句一直激勵我的座右銘，希望可以與大家共勉！