此文为学习极客时间中覃超的算法面试通关40讲所写

一、数组

1.理论

硬件保证只要给出数组的下标，只需要一次操作就可以拿到对应的值，所以查找的时间复杂度是O(1)。

插入和删除的平均的时间复杂度为O(n/2)，所以插入和删除的时间复杂度为O(n)。

2.练习题

a.两数之和

https://leetcode-cn.com/problems/two-sum/
(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 };
                }
            }
        }
        return null;
    }
}

因为使用了双层for循环，所以时间复杂度为O(n^2)，执行结果如下。

(2)解法二：利用HashMap

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(target - nums[i])) {
                return new int[] { i, map.get(target - nums[i]) };
            }
            // 将数组的值作为key，下标作为value存入map
            map.put(nums[i], i);
        }
        return null;
    }
}

因为只有一层for循环，且HashMap的添加和查找操作的时间复杂度为O(1)，所以这个算法的时间复杂度为O(n)，执行结果大大的优于解法一。

二、链表

1.理论

因为链表查找一个元素需要从头开始，所以查找的时间复杂度是O(n)。
插入和删除的时候步骤为常数次所以时间复杂度为O(1)。

2.练习题

a.反转链表

https://leetcode-cn.com/problems/reverse-linked-list/

(1)解法一

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode newNode = null;
        ListNode currentNode = head;
        while (currentNode != null) {
            ListNode tempNode = currentNode;
            currentNode = currentNode.next;
            tempNode.next = newNode;
            newNode = tempNode;
        }
        return newNode;
    }
}

因为要遍历所有节点，所以时间复杂度为O(n),执行结果如下。