一.数组

1.稀疏数组

当一个数组大部分元素为0，或者为同一个值的数组时，可以用稀疏数组来保存该数组
（1）记录数组有几行几列，有多少个不同的值
（2）把具有不同值的元素的行列值记录在一个小规模的数组中

//二维数组转稀疏数组
    private static int[][] parseSparseArray(int[][] array){
        //得到非0元素个数
        int sum = 0;
        int len = array.length;
        int height = array[0].length;
        for (int i = 0; i < len; i++){
            for (int j = 0; j < height; j++){
                if (array[i][j] != 0 ){
                    sum += 1;
                }
            }
        }
        int[][] result = new int[sum + 1][3];
        //为稀疏数组第一行赋值
        result[0][0] = len;
        result[0][1] = height;
        result[0][2] = sum;
        //为剩余行赋值
        int flag = 1;
        for (int i = 0; i < len; i++){
            for (int j = 0; j < height; j++){
                if (array[i][j] != 0){
                    result[flag][0] = i;
                    result[flag][1] = j;
                    result[flag][2] = array[i][j];
                    flag++;
                }
            }
        }
        return result;
    }

2.数组实现队列

public class ArrayParse2Queue {
    public ArrayParse2Queue(int maxSize){
        queue = new int[maxSize];
        front = -1; //指向第一个元素的前一个元素
        rear = -1; //指向最后一个元素
        this.maxSize = maxSize;
    }

    //判满
    public boolean isFull(){
        return rear == maxSize -1;
    }
    //判空
    public boolean isempty(){
        return rear == front;
    }
    //入队
    public void push(int a){
        if (isFull()){
            throw new RuntimeException("队列已满");
        }
        queue[++rear] = a;
    }
    //出队
    public int pop(){
        if (isempty()){
            throw new RuntimeException("队列已空");
        }
        int temp = queue[front+1];
        front ++;
        return temp;
    }
    //打印队列
    public void printQueue(){
        for (int i = front+1; i <= rear; i++){
            System.out.print(queue[i] + " ");
        }
    }
}

3.数组实现环形队列

由于在用数组实现队列的时候，队列有元素出列，front就向后移动，所以队列前面的空间就空了出来。当rear移动到LENGTH时，再入队会发生假溢出，也就是说实际上我们开辟的数组还有剩余空间，却因为rear越界表现为溢出，
为了更合理的利用空间，人们想了一个办法：将队列的首尾相连接。这样当rear移动到LENGTH时，会再从0开始循环
那当什么时候队列满呢？当rear等于front的时候。可是队列为空的时候也是同样的条件，那不就没法判断了吗？牺牲一个存储空间，front前面不存数据，当rear在front前面的时候就是满了（尾在头前就是满了）

队空条件：front == rear

队满条件：(rear+1) %QueueSize == front

队列长度：(rear—front + QueueSize) % QueueSize
（当rear > front时，此时队列的长度为rear—front。但当rear < front时，队列长度分为两段，一段是QueueSize-front，另一段是0 + rear，加在一起，队列长度为rear-front + QueueSize，）

public class CircleQueue {
    
    int front;
    int rear;
    int[] queue;
    int maxSize;

    public CircleQueue(int maxSize){
        queue = new int[maxSize];
        front = 0; //指向第一个元素的前一个元素
        rear = 0; //指向最后一个元素
        this.maxSize = maxSize;
    }

    //判满
    public boolean isFull(){
        return (rear + 1) % maxSize == front;
    }
    //判空
    public boolean isempty(){
        return rear == front;
    }
    //入队
    public void push(int a){
        if (isFull()){
            throw new RuntimeException("队列已满");
        }
        queue[rear] = a;
        rear = (rear + 1) % maxSize;
    }
    //出队
    public int pop(){
        if (isempty()){
            throw new RuntimeException("队列已空");
        }
        int temp = queue[front];
        front = (front + 1) % maxSize;
        return temp;
    }
    //打印队列
    public void printQueue(){
        for (int i = front; i < front + size(); i++){
            System.out.print(queue[i] + " ");
        }
    }
    //队列长度
    public int size(){
        return (rear + maxSize -front) % maxSize;
    }
}

4.leetcode-1 两数之和

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素

示例:给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
（1）暴力法

class Solution {
    public int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[j] == target - nums[i]) {
                    return new int[] { i, j };
                }
            }
        }
        throw new IllegalArgumentException("No two sum solution");
    }
}

（2）哈希表
在进行迭代并将元素插入到表中的同时，我们还会回过头来检查表中是否已经存在当前元素所对应的目标元素。如果它存在，那我们已经找到了对应解，并立即将其返回

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (map.containsKey(complement)) {
                return new int[] { map.get(complement), i };
            }
            map.put(nums[i], i);
        }
        throw new IllegalArgumentException("No two sum solution");
    }
}