数组是程序种最常见，最基本的数据结构
1、数组要灵活利用下标索引来快速访问到数组中指定的元素
2、数组的元素在内存中是连续存储的，每个元素占用的内存大小是一样的

这里通过练习leetcode的几道题目来加深对数组的学习

一 丶两数之和

这道题是 Leetcode 上的第（1）道题，给定一个数组和一个目标值，返回数组中两个元素之和为目标值的元素下标

1.1 暴力解法

即是使用遍历数组的方式，对所有的两数之和和目标值作比较，如相同则返回

  1. public int[] fun1(int[] nums, int target) {
  2.     for (int i = 0; i < nums.length; i++) {
  3.         for (int j = i + 1; j < nums.length; j++) {
  4.             if (nums[i] + nums[j] == target) {
  5.                 int[] res = new int[2];
  6.                 res[0] = i;
  7.                 res[1] = j;
  8.                 return res;
  9.             }
  10.         }
  11.     }
  12.     return null;
  13. }

复杂度：
时间复杂度：O（n^2），因为使用两个for循环，当最差的情况时，需要经过 n(n-1) 次才能找到目标值
空间复杂度：O（1）

1.2 哈希表

遍历一次元素，将元素和目标值的差值，和哈希表中的key作比较，若存在于哈希表中，则返回，若不存在，则将元素插入到哈希表当中

  1. public int[] fun2(int[] nums, int target) {
  2.     HashMap<Integer, Integer> map = new HashMap<>();
  3.     for (int i = 0; i < nums.length; i++) {
  4.         int temp = target - nums[i];
  5.         if (map.containsKey(temp)) {
  6.             return new int[]{i, map.get(temp)};
  7.         } else {
  8.             map.put(nums[i], i);
  9.         }
  10.     }
  11.     return null;
  12. }

二丶三数之和

LeetCode上第（15）题
给定一个数组，找出三个元素之和为目标值0的所有组合

3.1 暴力法

暴力法循环三次后，得到一个集合，但是这个集合是没有去重的

  1. public List<List<Integer>> fun1(int[] nums) {
  2.     int len = nums.length;
  3.     ArrayList<List<Integer>> list = new ArrayList<>();
  4.     for (int i = 0; i < len - 2; i++) {
  5.         for (int j = i + 1; j < len - 1; j++) {
  6.             for (int k = j + 1; k < len; k++) {
  7.                 if (nums[i] + nums[j] + nums[k] == 0) {
  8.                     list.add(Arrays.asList(nums[i], nums[j], nums[k]));
  9.                 }
  10.             }
  11.         }
  12.     }
  13.     return list;
  14. }

3.2 哈希表