算法之数组篇

基础

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

• 数组下标都是从0开始的。
• 数组内存空间的地址是连续的。
• 数组的元素是不能删的，只能覆盖。

vector和array的区别：vector的底层实现是array，严格来讲vector是容器，不是数组。

解题方法

遇到数组题目一般解题方法有

• 二分法
  • 左闭右闭、左闭右开
• 双指针法
  • 快慢指针、从左到右和从右到左的指针
• 滑动窗口
  • 像窗户一样的滑动，动态更新子序列
• 模拟算法
  • 对题目进行一个演示模拟的行为

代码演练

二分法
力扣题目链接704

    int search(vector<int>& nums, int target) {
        // 写法一 左闭右闭
    //    int left = 0, right = nums.size()-1;
    //    while (left <= right)
    //    {
    //        int middle = (left + right) / 2;
    //        if (nums[middle] < target)
    //            left = middle + 1;
    //       else if (nums[middle] > target)
    //            right = middle - 1;
    //        else
    //            return middle;
    //    }
    //    return -1;
    // }

        // 写法二 左闭右开
        int left = 0, right = nums.size();
        while (left < right)
        {
            int middle = (left + right) / 2;
            if (nums[middle] < target)
                left = middle + 1;
            else if (nums[middle] > target)
                right = middle;
            else
                return middle;
        }
        return -1;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

双指针法
力扣题目链接977

vector<int> sortedSquares(vector<int>& nums) {
        int k = nums.size();

        vector <int> res(k);
        k--;
        int l = 0, r = nums.size() - 1;
        while (l <= r)
        {
            if (nums[l] * nums[l] < nums[r] * nums[r])
            {
                res[k--] = nums[r] * nums[r];
                r--;
            }
            else
            {
                res[k--] = nums[l] * nums[l];
                l++;
            }
        }
        return res;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

滑动窗口法
力扣题目链接977

 vector<int> sortedSquares(vector<int>& nums) {
        int k = nums.size();

        vector <int> res(k);
        k--;
        int l = 0, r = nums.size() - 1;
        while (l <= r)
        {
            if (nums[l] * nums[l] < nums[r] * nums[r])
            {
                res[k--] = nums[r] * nums[r];
                r--;
            }
            else
            {
                res[k--] = nums[l] * nums[l];
                l++;
            }
        }
        return res;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

模拟算法

• 即用代码实现进行对题目的模仿，用代码实现一种思想的行为；

总结

数组是存放在连续内存空间上的相同类型数据的集合。
数组可以方便的通过下标索引的方式获取到下标下对应的数据。
数组的查询查询效率很高，时间复杂度为O(1);
运用不同的解题方法会对执行效率产生不同的影响；合适的解题方法会使时间复杂度降低，执行效率更高。