目錄
- 1.求兩數之和
- 思路：
- 代碼實作：
- 1.當前采用暴力解法
- 2.采用Map集合解法
- 2.洗掉排序陣列中的重復項
- 思路：
- 代碼實作：
1.求兩數之和
給定一個整數陣列 nums 和一個目標值 target，請你在該陣列中找出和為目標值的那 兩個 整數，并回傳他們的陣列下標，
你可以假設每種輸入只會對應一個答案，但是，陣列中同一個元素不能使用兩遍，
示例:
給定 nums = [2, 7, 11, 15], target = 9
因為 nums[0] + nums[1] = 2 + 7 = 9
所以回傳 [0, 1]
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/two-sum
思路：
? 利用雙層for回圈，定義兩個指標i，j；
? 看第i個數與第i個數以后的數相加是否為target目標值，若相等則回傳i，j的索引位置；否則i++，
代碼實作：
1.當前采用暴力解法
class Solution {
public int[] twoSum(int[] nums, int target) {
for (int i=0;i<nums.length-1;i++){
for (int j = i+1; j < nums.length ; j++) {
if((nums[i] + nums[j]) == target){
return new int[]{i,j};
}
}
}
throw new IllegalArgumentException("no two sum solution");
}
}
2.采用Map集合解法
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
// 將陣列中的值和陣列下標對應存入map集合中
for (int i = 0; i < nums.length; i++) {
map.put(nums[i], i);
}
for (int j = 0; j < nums.length; j++) {
int comp = target - nums[j];
if (map.containsKey(comp)&&map.get(comp)!=j) {
return new int[]{j,map.get(comp)};
}
}
throw new IllegalArgumentException("No two sum solution");
}
}
ps: 采用Map集合實作將索引和陣列中的資料進行一一對應，采用單重for回圈將時間復雜度從O(n^2)降至O（n）;利用containsKey判斷是否存在所求值，利用get排除索引號相同的情況，
2.洗掉排序陣列中的重復項
? 給定一個排序陣列，你需要在 原地 洗掉重復出現的元素，使得每個元素只出現一次，回傳移除后陣列的新長度，
? 不要使用額外的陣列空間，你必須在 原地 修改輸入陣列 并在使用 O(1) 額外空間的條件下完成，
示例 1:
? 給定陣列 nums = [1,1,2],
? 函式應該回傳新的長度 2, 并且原陣列 nums 的前兩個元素被修改為 1, 2，
? 你不需要考慮陣列中超出新長度后面的元素，
示例 2:
? 給定 nums = [0,0,1,1,1,2,2,3,3,4],
? 函式應該回傳新的長度 5, 并且原陣列 nums 的前五個元素被修改為 0, 1, 2, 3, 4，
? 你不需要考慮陣列中超出新長度后面的元素，
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array
思路：
? 利用快慢指標，
? 倘若慢指標指向的值與快指標的值不相同，則慢指標+1；將快指標的值賦給慢指標所在位置，
? 最后回傳慢指標數+1即可
代碼實作：
class Solution {
public int removeDuplicates(int[] nums) {
// 如果陣列為空
if (nums.length == 0){
return 0;
}
// 定義快慢指標,i為慢指標，為快指標
int i=0,j=1;
for (;j < nums.length; j++) {
if(nums[j] != nums[i]){
i++;
nums[i] = nums[j];
}
}
return i+1;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/135499.html
標籤：其他