数组双指针遍历场景

Dear 丶 2024-03-23 16:29 18阅读 0赞

# 下标为5可以获取到什么信息？
    
    1、下标为5
    2、前面有4个元素
    3、当前为第6号元素
    4、后面有4个元素（10-4）
    5、倒数第5

--------------------

# 下标m到n一个多少个元素？
    
    0-1-2-3-4
    0-1-2-3-4-5-6-7
    
    1、第2组比第一组多7-4=3个元素
    2、4到7有7-4+1个元素（多的3个加上3本身共4个）

--------------------

# 1、数组折叠 对应下标相加为 length-1
    
    a  b  c  c  b  a
    0  1  2  3  4  5
    0+5=5
    1+4=5
    2+3=5
    
    a  b  c  b  a  
    0  1  2  3  4  
    0+4=4
    1+3=4
    2+2=4
    
    # 2、i 和 arr.length-1-i 是前后遥相呼应的两个位置

--------------------

# 区间[0,arr.length/2) 为数组左一半
    
    abcba  ☞ 长度为奇数时 arr.length()/2 ☞ 5/2=2 ☞ [0 1] ② 3 4
    abccba ☞ 长度为偶数时 arr.length()/2 ☞ 6/2=3 ☞ [0 1 2] ③ 4 5

**[NC17 最长回文子串][NC17]**  
**[Java 业务原子级常用方法 ☞ 判断子串是不是回文子串][Java _ _]**

--------------------

## 参考： ##

**[数组遍历 ☞ 第1波学习总结][_ _1]**  
**[数组遍历 ☞ 第2波学习总结][_ _2]**  
**[数组遍历 ☞ 第3波学习总结][_ _3]**

--------------------

### 一维数据遍历 ###

int[] arr = new int[]{
        1, 2, 3, 4, 5, 6, 7, 8, 9};
    
    # 正序
    for (int i = 0; i < arr.length; i++) {
        
        System.out.print(arr[i] + " ");
    }
    1 2 3 4 5 6 7 8 9 
    
    # 逆序
    for (int i = arr.length - 1; i >= 0; i--) {
        
        System.out.print(arr[i] + " ");
    }
    9 8 7 6 5 4 3 2 1

--------------------

### \[数组遍历\]这个行为被重复执行 ###

int[] arr = new int[]{
        1, 2, 3, 4, 5, 6, 7, 8, 9};
    
    // 控制[数组遍历]这个行为被重复执行次数--正序逆序不重要
    for (int i = 0; i < arr.length; i++) {
        
    // for (int i = arr.length - 1; i >= 0; i--) {
        
        
        // 数组正序遍历的行为
        for (int j = 0; j < arr.length; j++) {
        
            System.out.print(arr[j] + "  ");
        }
        
        System.out.print("←分水岭→  ");
        
        // 数组逆序遍历的行为
        for (int k = arr.length - 1; k >= 0; k--) {
        
            System.out.print(arr[k] + "  ");
        }
        System.out.println();
    }
    
    1  2  3  4  5  6  7  8  9  ←分水岭→  9  8  7  6  5  4  3  2  1  
    1  2  3  4  5  6  7  8  9  ←分水岭→  9  8  7  6  5  4  3  2  1  
    1  2  3  4  5  6  7  8  9  ←分水岭→  9  8  7  6  5  4  3  2  1  
    1  2  3  4  5  6  7  8  9  ←分水岭→  9  8  7  6  5  4  3  2  1  
    1  2  3  4  5  6  7  8  9  ←分水岭→  9  8  7  6  5  4  3  2  1  
    1  2  3  4  5  6  7  8  9  ←分水岭→  9  8  7  6  5  4  3  2  1  
    1  2  3  4  5  6  7  8  9  ←分水岭→  9  8  7  6  5  4  3  2  1  
    1  2  3  4  5  6  7  8  9  ←分水岭→  9  8  7  6  5  4  3  2  1  
    1  2  3  4  5  6  7  8  9  ←分水岭→  9  8  7  6  5  4  3  2  1  
    
    1  2  3  4  5  6  7  8  9  ←分水岭→  9  8  7  6  5  4  3  2  1
    1  2  3  4  5  6  7  8  9  ←分水岭→  9  8  7  6  5  4  3  2  1
    1  2  3  4  5  6  7  8  9  ←分水岭→  9  8  7  6  5  4  3  2  1
    1  2  3  4  5  6  7  8  9  ←分水岭→  9  8  7  6  5  4  3  2  1
    1  2  3  4  5  6  7  8  9  ←分水岭→  9  8  7  6  5  4  3  2  1
    1  2  3  4  5  6  7  8  9  ←分水岭→  9  8  7  6  5  4  3  2  1
    1  2  3  4  5  6  7  8  9  ←分水岭→  9  8  7  6  5  4  3  2  1
    1  2  3  4  5  6  7  8  9  ←分水岭→  9  8  7  6  5  4  3  2  1
    1  2  3  4  5  6  7  8  9  ←分水岭→  9  8  7  6  5  4  3  2  1

--------------------

### \[数组元素\]被重复执行 ###

int[] arr = new int[]{
        1, 2, 3, 4, 5, 6, 7, 8, 9};
    
    // 数组元素排队轮回的顺序--正序 or 逆序
    for (int i = 0; i < arr.length; i++) {
        
    // for (int i = arr.length - 1; i >= 0; i--) {
        
    
        // 控制[数组元素]被重复执行次数--正序逆序不重要
        for (int j = 0; j < arr.length; j++) {
        
            System.out.print(arr[i] + "  ");
        }
        
        System.out.print("←分水岭→  ");
        
        // 控制[数组元素]被重复执行次数--正序逆序不重要
        for (int k = arr.length - 1; k >= 0; k--) {
        
            System.out.print(arr[i] + "  ");
        }
        System.out.println();
    }
    
    1  1  1  1  1  1  1  1  1  ←分水岭→  1  1  1  1  1  1  1  1  1
    2  2  2  2  2  2  2  2  2  ←分水岭→  2  2  2  2  2  2  2  2  2
    3  3  3  3  3  3  3  3  3  ←分水岭→  3  3  3  3  3  3  3  3  3
    4  4  4  4  4  4  4  4  4  ←分水岭→  4  4  4  4  4  4  4  4  4
    5  5  5  5  5  5  5  5  5  ←分水岭→  5  5  5  5  5  5  5  5  5
    6  6  6  6  6  6  6  6  6  ←分水岭→  6  6  6  6  6  6  6  6  6
    7  7  7  7  7  7  7  7  7  ←分水岭→  7  7  7  7  7  7  7  7  7
    8  8  8  8  8  8  8  8  8  ←分水岭→  8  8  8  8  8  8  8  8  8
    9  9  9  9  9  9  9  9  9  ←分水岭→  9  9  9  9  9  9  9  9  9
    
    9  9  9  9  9  9  9  9  9  ←分水岭→  9  9  9  9  9  9  9  9  9
    8  8  8  8  8  8  8  8  8  ←分水岭→  8  8  8  8  8  8  8  8  8
    7  7  7  7  7  7  7  7  7  ←分水岭→  7  7  7  7  7  7  7  7  7
    6  6  6  6  6  6  6  6  6  ←分水岭→  6  6  6  6  6  6  6  6  6
    5  5  5  5  5  5  5  5  5  ←分水岭→  5  5  5  5  5  5  5  5  5
    4  4  4  4  4  4  4  4  4  ←分水岭→  4  4  4  4  4  4  4  4  4
    3  3  3  3  3  3  3  3  3  ←分水岭→  3  3  3  3  3  3  3  3  3
    2  2  2  2  2  2  2  2  2  ←分水岭→  2  2  2  2  2  2  2  2  2
    1  1  1  1  1  1  1  1  1  ←分水岭→  1  1  1  1  1  1  1  1  1

--------------------

### 动态规划里总结出来的 ☞ 回放的思想 ###

int[] arr = new int[]{
        1, 2, 3, 4, 5, 6, 7, 8, 9};
    
    for (int i = 0; i < arr.length; i++) {
        
        // 从0回放到i
        // for (int j = 0; j <= i; j++) {
        
        
        // 从i回退到0
        // for (int j = i; j >= 0; j--) {
        
        
        // 从i快进到arr.length-1
        // for (int j = i; j < arr.length; j++) {
        
        
        // 从arr.length-1回退到i
        for (int j = arr.length - 1; j >= i; j--) {
        
            System.out.print(arr[j] + "  ");
        }
        System.out.println();
    }
    
    1                          ←分水岭→  1                          ←分水岭→  1  2  3  4  5  6  7  8  9  ←分水岭→  9  8  7  6  5  4  3  2  1
    1  2                       ←分水岭→  2  1                       ←分水岭→  2  3  4  5  6  7  8  9     ←分水岭→  9  8  7  6  5  4  3  2   
    1  2  3                    ←分水岭→  3  2  1                    ←分水岭→  3  4  5  6  7  8  9        ←分水岭→  9  8  7  6  5  4  3      
    1  2  3  4                 ←分水岭→  4  3  2  1                 ←分水岭→  4  5  6  7  8  9           ←分水岭→  9  8  7  6  5  4         
    1  2  3  4  5              ←分水岭→  5  4  3  2  1              ←分水岭→  5  6  7  8  9              ←分水岭→  9  8  7  6  5            
    1  2  3  4  5  6           ←分水岭→  6  5  4  3  2  1           ←分水岭→  6  7  8  9                 ←分水岭→  9  8  7  6               
    1  2  3  4  5  6  7        ←分水岭→  7  6  5  4  3  2  1        ←分水岭→  7  8  9                    ←分水岭→  9  8  7                  
    1  2  3  4  5  6  7  8     ←分水岭→  8  7  6  5  4  3  2  1     ←分水岭→  8  9                       ←分水岭→  9  8                     
    1  2  3  4  5  6  7  8  9  ←分水岭→  9  8  7  6  5  4  3  2  1  ←分水岭→  9                          ←分水岭→  9

--------------------

### 元素遍历其下标的次数 ☞ 还未在算法中遇到 ###

int[] arr = new int[]{
        1, 2, 3, 4, 5, 6, 7, 8, 9};
    for (int i = 0; i < arr.length; i++) {
        
        // 位置i处元素遍历i次，正序，逆序无所谓
        // for (int j = 0; j <= i; j++) {
        
        // for (int j = i; j >= 0; j--) {
        
        
        // 位置i处元素遍历arr.length-i次，正序逆序无所谓
        // for (int j = i; j < arr.length; j++) {
        
        for (int j = arr.length - 1; j >= i; j--) {
        
            System.out.print(arr[i] + "  ");
        }
        System.out.println();
    }
    
    1                          ←分水岭→  1                          ←分水岭→  1  1  1  1  1  1  1  1  1  ←分水岭→  1  1  1  1  1  1  1  1  1
    2  2                       ←分水岭→  2  2                       ←分水岭→  2  2  2  2  2  2  2  2     ←分水岭→  2  2  2  2  2  2  2  2   
    3  3  3                    ←分水岭→  3  3  3                    ←分水岭→  3  3  3  3  3  3  3        ←分水岭→  3  3  3  3  3  3  3      
    4  4  4  4                 ←分水岭→  4  4  4  4                 ←分水岭→  4  4  4  4  4  4           ←分水岭→  4  4  4  4  4  4         
    5  5  5  5  5              ←分水岭→  5  5  5  5  5              ←分水岭→  5  5  5  5  5              ←分水岭→  5  5  5  5  5            
    6  6  6  6  6  6           ←分水岭→  6  6  6  6  6  6           ←分水岭→  6  6  6  6                 ←分水岭→  6  6  6  6               
    7  7  7  7  7  7  7        ←分水岭→  7  7  7  7  7  7  7        ←分水岭→  7  7  7                    ←分水岭→  7  7  7                  
    8  8  8  8  8  8  8  8     ←分水岭→  8  8  8  8  8  8  8  8     ←分水岭→  8  8                       ←分水岭→  8  8                     
    9  9  9  9  9  9  9  9  9  ←分水岭→  9  9  9  9  9  9  9  9  9  ←分水岭→  9                          ←分水岭→  9

--------------------

### 基于目标的博弈 ☞ 回放的思想 ###

int[] arr = new int[]{
        1, 2, 3, 4, 5, 6, 7, 8, 9};
    
    for (int i = 0; i < arr.length; i++) {
        
        // 逐级降低目标
        for (int j = 0; j <= arr.length - 1 - i; j++) {
        
        // 逐级降低目标 ☞ 基于右边界的思想
        // for (int j = 0; j < arr.length - i; j++) {
        
            str += arr[j] + "  ";
        }
        
        // 从arr.length-1回退到i (相同功能)
        for (int j = arr.length - 1 - i; j >= 0; j--) {
        
            str += arr[j] + "  ";
        }
        
        // 降低成本，观察是否还能达到预期目标
        for (int j = arr.length - 1 - i; j < arr.length; j++) {
        
            str += arr[j] + "  ";
        }
        
        // 资本对品质的反向蚕食
        for (int j = arr.length - 1; j >= arr.length - 1 - i; j--) {
        
            str += arr[j] + "  ";
        }
    }
        
    1  2  3  4  5  6  7  8  9  ←分水岭→  9  8  7  6  5  4  3  2  1  ←分水岭→  9                          ←分水岭→  9                         
    1  2  3  4  5  6  7  8     ←分水岭→  8  7  6  5  4  3  2  1     ←分水岭→  8  9                       ←分水岭→  9  8                      
    1  2  3  4  5  6  7        ←分水岭→  7  6  5  4  3  2  1        ←分水岭→  7  8  9                    ←分水岭→  9  8  7                   
    1  2  3  4  5  6           ←分水岭→  6  5  4  3  2  1           ←分水岭→  6  7  8  9                 ←分水岭→  9  8  7  6                
    1  2  3  4  5              ←分水岭→  5  4  3  2  1              ←分水岭→  5  6  7  8  9              ←分水岭→  9  8  7  6  5             
    1  2  3  4                 ←分水岭→  4  3  2  1                 ←分水岭→  4  5  6  7  8  9           ←分水岭→  9  8  7  6  5  4          
    1  2  3                    ←分水岭→  3  2  1                    ←分水岭→  3  4  5  6  7  8  9        ←分水岭→  9  8  7  6  5  4  3       
    1  2                       ←分水岭→  2  1                       ←分水岭→  2  3  4  5  6  7  8  9     ←分水岭→  9  8  7  6  5  4  3  2    
    1                          ←分水岭→  1                          ←分水岭→  1  2  3  4  5  6  7  8  9  ←分水岭→  9  8  7  6  5  4  3  2  1

### 元素遍历其\[下标的对折位置的下标\]的次数（前→后） ###

int[] arr = new int[]{
        1, 2, 3, 4, 5, 6, 7, 8, 9};
    
    for (int i = 0; i < arr.length; i++) {
        
        // 元素遍历其[下标的对折位置的下标]的次数，正序逆序无所谓
        for (int j = 0; j <= arr.length - 1 - i; j++) {
        
            str += arr[i] + "  ";
        }
        // 元素遍历其[下标的对折位置的下标]的次数，正序逆序无所谓
        for (int j = arr.length - 1 - i; j >= 0; j--) {
        
            str += arr[i] + "  ";
        }
        // 元素遍历其下标的次数，正序逆序无所谓
        for (int j = arr.length - 1 - i; j < arr.length; j++) {
        
            str += arr[i] + "  ";
        }
        // 元素遍历其下标的次数，正序逆序无所谓
        for (int j = arr.length - 1; j >= arr.length - 1 - i; j--) {
        
            str += arr[i] + "  ";
        }
    }
    
    1  1  1  1  1  1  1  1  1  ←分水岭→  1  1  1  1  1  1  1  1  1  ←分水岭→  1                          ←分水岭→  1                        
    2  2  2  2  2  2  2  2     ←分水岭→  2  2  2  2  2  2  2  2     ←分水岭→  2  2                       ←分水岭→  2  2                     
    3  3  3  3  3  3  3        ←分水岭→  3  3  3  3  3  3  3        ←分水岭→  3  3  3                    ←分水岭→  3  3  3                  
    4  4  4  4  4  4           ←分水岭→  4  4  4  4  4  4           ←分水岭→  4  4  4  4                 ←分水岭→  4  4  4  4               
    5  5  5  5  5              ←分水岭→  5  5  5  5  5              ←分水岭→  5  5  5  5  5              ←分水岭→  5  5  5  5  5            
    6  6  6  6                 ←分水岭→  6  6  6  6                 ←分水岭→  6  6  6  6  6  6           ←分水岭→  6  6  6  6  6  6         
    7  7  7                    ←分水岭→  7  7  7                    ←分水岭→  7  7  7  7  7  7  7        ←分水岭→  7  7  7  7  7  7  7      
    8  8                       ←分水岭→  8  8                       ←分水岭→  8  8  8  8  8  8  8  8     ←分水岭→  8  8  8  8  8  8  8  8   
    9                          ←分水岭→  9                          ←分水岭→  9  9  9  9  9  9  9  9  9  ←分水岭→  9  9  9  9  9  9  9  9  9

### 回放的思想 ☞ 基于数组折叠思想 ###

int[] arr = new int[]{
        1, 2, 3, 4, 5, 6, 7, 8, 9};
    
    for (int i = arr.length - 1; i >= 0; i--) {
        
        for (int j = 0; j <= arr.length - 1 - i; j++) {
        
            str += arr[j] + "  ";
        }
        for (int j = arr.length - 1 - i; j >= 0; j--) {
        
            str += arr[j] + "  ";
        }
        for (int j = arr.length - 1 - i; j < arr.length; j++) {
        
            str += arr[j] + "  ";
        }
        for (int j = arr.length - 1; j >= arr.length - 1 - i; j--) {
        
            str += arr[j] + "  ";
        }
    }
    
    
    1                          ←分水岭→  1                          ←分水岭→  1  2  3  4  5  6  7  8  9  ←分水岭→  9  8  7  6  5  4  3  2  1  
    1  2                       ←分水岭→  2  1                       ←分水岭→  2  3  4  5  6  7  8  9     ←分水岭→  9  8  7  6  5  4  3  2     
    1  2  3                    ←分水岭→  3  2  1                    ←分水岭→  3  4  5  6  7  8  9        ←分水岭→  9  8  7  6  5  4  3        
    1  2  3  4                 ←分水岭→  4  3  2  1                 ←分水岭→  4  5  6  7  8  9           ←分水岭→  9  8  7  6  5  4           
    1  2  3  4  5              ←分水岭→  5  4  3  2  1              ←分水岭→  5  6  7  8  9              ←分水岭→  9  8  7  6  5              
    1  2  3  4  5  6           ←分水岭→  6  5  4  3  2  1           ←分水岭→  6  7  8  9                 ←分水岭→  9  8  7  6                 
    1  2  3  4  5  6  7        ←分水岭→  7  6  5  4  3  2  1        ←分水岭→  7  8  9                    ←分水岭→  9  8  7                    
    1  2  3  4  5  6  7  8     ←分水岭→  8  7  6  5  4  3  2  1     ←分水岭→  8  9                       ←分水岭→  9  8                       
    1  2  3  4  5  6  7  8  9  ←分水岭→  9  8  7  6  5  4  3  2  1  ←分水岭→  9                          ←分水岭→  9

### 元素遍历其\[下标的对折位置的下标\]的次数（后→前） ###

int[] arr = new int[]{
        1, 2, 3, 4, 5, 6, 7, 8, 9};
    
    for (int i = arr.length - 1; i >= 0; i--) {
        
        // 元素遍历其[下标的对折位置的下标]的次数，正序逆序无所谓
        for (int j = 0; j <= arr.length - 1 - i; j++) {
        
            str += arr[i] + "  ";
        }
        // 元素遍历其[下标的对折位置的下标]的次数，正序逆序无所谓
        for (int j = arr.length - 1 - i; j >= 0; j--) {
        
            str += arr[i] + "  ";
        }
        // 元素遍历其下标的次数，正序逆序无所谓
        for (int j = arr.length - 1 - i; j < arr.length; j++) {
        
            str += arr[i] + "  ";
        }
        // 元素遍历其下标的次数，正序逆序无所谓
        for (int j = arr.length - 1; j >= arr.length - 1 - i; j--) {
        
            str += arr[i] + "  ";
        }
    }
    
    
    9                          ←分水岭→  9                          ←分水岭→  9  9  9  9  9  9  9  9  9  ←分水岭→  9  9  9  9  9  9  9  9  9
    8  8                       ←分水岭→  8  8                       ←分水岭→  8  8  8  8  8  8  8  8     ←分水岭→  8  8  8  8  8  8  8  8   
    7  7  7                    ←分水岭→  7  7  7                    ←分水岭→  7  7  7  7  7  7  7        ←分水岭→  7  7  7  7  7  7  7      
    6  6  6  6                 ←分水岭→  6  6  6  6                 ←分水岭→  6  6  6  6  6  6           ←分水岭→  6  6  6  6  6  6         
    5  5  5  5  5              ←分水岭→  5  5  5  5  5              ←分水岭→  5  5  5  5  5              ←分水岭→  5  5  5  5  5            
    4  4  4  4  4  4           ←分水岭→  4  4  4  4  4  4           ←分水岭→  4  4  4  4                 ←分水岭→  4  4  4  4               
    3  3  3  3  3  3  3        ←分水岭→  3  3  3  3  3  3  3        ←分水岭→  3  3  3                    ←分水岭→  3  3  3                  
    2  2  2  2  2  2  2  2     ←分水岭→  2  2  2  2  2  2  2  2     ←分水岭→  2  2                       ←分水岭→  2  2                     
    1  1  1  1  1  1  1  1  1  ←分水岭→  1  1  1  1  1  1  1  1  1  ←分水岭→  1                          ←分水岭→  1

### 数组范围截取 ###

int[] arr = new int[]{
        1, 2, 3, 4, 5, 6, 7, 8, 9};
    for (int i = 0; i < arr.length; i++) {
        
        for (int j = 0; j < arr.length; j++) {
        
            str += arr[i] + "  ";
        }
    }
    for (int i = 1; i < arr.length; i++) {
        
        for (int j = 1; j < arr.length; j++) {
        
            str1 += arr[j] + "  ";
        }
    }
    for (int i = arr.length - 1; i < arr.length; i++) {
        
        for (int j = arr.length - 1; j < arr.length; j++) {
        
            str1 += arr[j] + "  ";
        }
    }
    
    1  1  1  1  1  1  1  1  1
    2  2  2  2  2  2  2  2  2
    3  3  3  3  3  3  3  3  3
    4  4  4  4  4  4  4  4  4
    5  5  5  5  5  5  5  5  5
    6  6  6  6  6  6  6  6  6
    7  7  7  7  7  7  7  7  7
    8  8  8  8  8  8  8  8  8
    9  9  9  9  9  9  9  9  9
    
       2  2  2  2  2  2  2  2
       3  3  3  3  3  3  3  3
       4  4  4  4  4  4  4  4
       5  5  5  5  5  5  5  5
       6  6  6  6  6  6  6  6
       7  7  7  7  7  7  7  7
       8  8  8  8  8  8  8  8
       9  9  9  9  9  9  9  9
       
                            9

[NC17]: https://blog.csdn.net/weixin_37646636/article/details/129033393
[Java _ _]: https://blog.csdn.net/weixin_37646636/article/details/128673074
[_ _1]: https://blog.csdn.net/weixin_37646636/article/details/119835229
[_ _2]: https://blog.csdn.net/weixin_37646636/article/details/125754146
[_ _3]: https://blog.csdn.net/weixin_37646636/article/details/130318990