数组理论基础

数组是存放在连续内存空间上的相同类型数据的集合。

  • 数组下标都是从0开始的
  • 数组内存空间的地址是连续的

数组的元素不能删，只能覆盖

704.二分查找

文章：2. 二分查找

题目：704. 二分查找

【思路】

左闭右闭区间

  • Go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func search(nums []int, target int) int {
    //左闭右闭区间
    left,right := 0,len(nums)-1 //!!
    //(left + right) / 2 = left/2 + right/2
    //left + ((right - left)/2)
    //left + right/2 - left/2 = right/2 + left/2
    for ;left <= right ; {
        mid := left + (right - left)/2
        if nums[mid] == target{
            return mid
        }else if nums[mid] > target{
            right = mid - 1
        }else {
            left = mid + 1  
        }
    } 
    return -1

}
  • Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length-1; 
        while(left <= right){
            int mid = left + (right-left)/2;
            if(nums[mid] == target){
                return mid;
            }else if(nums[mid] > target){
                right = mid -1 ;
            }else{
                left = mid + 1;
            }
        }
        return -1;
    }
}

27.移除元素

文章：3. 移除元素

题目：27. 移除元素

【思路】

快慢指针

  • 快指针：寻找新数组的元素，不含有目标数组的数组

  • 慢指针：指向更新新数组下标的位置

  • Java实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int removeElement(int[] nums, int val) {
        //快慢指针
        int slow = 0;
        int fast =0;
        for(;fast < nums.length;fast++){
            if(nums[fast] != val){
                //更新
                nums[slow] = nums[fast];
                slow++;
            }
        }
        return slow;
    }
}
  • Go实现
1
2
3
4
5
6
7
8
9
10
func removeElement(nums []int, val int) int {
    slow,fast := 0,0
    for ;fast < len(nums);fast++{
        if nums[fast] != val{
            nums[slow] = nums[fast]
            slow++
        }
    }
    return slow
}