数组：小而美的算法技巧 前缀和、差分数组、花式遍历

class NumArray {
//定义前缀和数组 
int [] preSum;
/*构造前缀和数组 */ 
public NumArray(int[] nums) {
//nums数组的长度 
int n=nums.length;
//定义 前缀和preSum数组,preSum[i]表示nums数组从0到i-1个元素的和 
preSum=new int [n+1];
//preSum第一个元素为0 
preSum[0]=0;
for(int i=1;i<preSum.length;i++){
preSum[i]=preSum[i-1]+nums[i-1];
}
}
/* 查询闭区间 [left, right] 的累加和 */ 
public int sumRange(int left, int right) {
return preSum[right+1]-preSum[left];
}
}

输入一个数组nums，然后又要求给区间nums[2..6]全部加 1，再给nums[3..9]全部减 3，再给nums[0..4]全部加 2，再给…问最后nums数组的值是什么?

//差分数组
class Difference{
    //定义差分数组
    int [] diff;
    
    /*构造差分数组*/
    public Difference(int []nums){
        diff =new int[nums.length];
        //根据初始数据构造差分数组
        diff[0]=nums[0];
        for(int i=1;i<nums.length;i++){
            diff[i]=nums[i]-nums[i-1];
        }
    }
    
    /*对区间[i,j]进行增减,val为+，则为加法，val为-，则为减法*/
    public void increment(int i,int j,int val){
        diff[i]=diff[i]+val；
            if(j+1<diff.length){//当j+1>=diff.length时，说明对nums[i]及以后的整个数组都进行了修改，所以就不需要给diff减val了
                diff[j+1]=diff[j+1]-val;
            }
    }
    
    /*返回结果数组*/
    public int []result(){
        int res=new int[diff.length];
        //根据差分数组构造结果数组
        //nums[0]=diff[0]=res[0];
        res[0]=diff[0];
        for(int i=1;i<diff.length;i++){
            res[i]=res[i-1]+diff[i];
        }
        return res;
    }
}

int []getModifiedArray(int length,int[][] updates){
    //将nums全部初始化为0
    int []nums=new int[length];
    
    //构造差分解法
    Difference df=new Difference(nums);
    
    for(int []update :updates){
        int i=update[0];
        int j=upfate[1];
        int val=update[2];
        df.increment(i,j,val);
    }
    return df.result();
}

class Solution {
    /* 二维数组顺时针旋转90度 */
    public void rotate(int[][] matrix) {
        //获取数组的行数行：matrix.length
        //获取数组的列数：matrix[0].length
        int n=matrix.length;

        //延对角线镜像翻转二维矩阵
        for(int i=0;i<n;i++){
            for(int j=i;j<n;j++){
                //交换matrix[i][j]和matrix[j][i]
                int temp=matrix[i][j];
                matrix[i][j]=matrix[j][i];
                matrix[j][i]=temp;
        }
    }
    //反转二维数组的每一行
    for(int []row :matrix){
            reverse(row);
    }
}
    //反转一维数组
    public void reverse(int [] arr){
        int i=0,j=arr.length-1;
        while(j>i){
            //交换i,j的顺序
            int temp=arr[i];
            arr[i]=arr[j];
            arr[j]=temp;
            i++;
            j--;

        }
    } 
}