剑指Offer常见Java算法题解析：两数相加、最长无重复子串及求和技巧

Alice

发布时间：2026-10-16| 6人浏览过

原创

在面试与算法训练中，掌握基础数据结构的操作至关重要。本文针对四道经典Java算法题进行深度解析，涵盖链表的两数相加、基于滑动窗口的最长无重复字符子串查找，以及结合哈希统计与循环遍历的数组求和问题。通过具体代码示例与逻辑拆解，帮助读者理解核心解题思路与边界条件处理。

两数相加：模拟链表进位运算

该问题要求将两个非空链表表示的非负整数相加，并以相同形式返回一个新的链表。每个链表的节点按低位到高位存储，需模拟手算加法的进位逻辑。

第1步：初始化指针与进位变量

创建一个虚拟头结点 node 用于简化链表构建，ans 指向该头结点以便最终返回结果。carry 记录进位值，初始为0。

第2步：遍历链表同步计算

只要 l1 或 l2 不为空，就进入循环。取出当前节点的数值（若为空则为0），加上进位值得到总和 sum。新节点的值为 sum % 10，新的进位值为 sum / 10 >= 1 ? 1 : 0。

第3步：移动指针与收尾处理

更新 l1 和 l2 到下一个节点。当遍历结束后，若仍存在进位（carry >= 1），需在末尾追加一个值为1的新节点。最后返回 ans.next 即跳过虚拟头结点的真实结果链表。

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode node = new ListNode(-1);
        ListNode ans = node;
        int carry = 0;
        while (l1 != null || l2 != null) {
            int n1 = l1 != null ? l1.val : 0;
            int n2 = l2 != null ? l2.val : 0;
            int sum = n1+n2+carry;
            carry = 0;
            node.next = new ListNode(sum%10);
            node = node.next;
            if(sum/10>=1){
                carry = 1;
            }
            if(l1!=null){
                l1 = l1.next;
            }
            if(l2!=null){
                l2 = l2.next;
            }
        }
        if(carry>=1){
            node.next = new ListNode(1);
        }
        return ans.next;
    }
}

最长无重复字符子串：滑动窗口应用

给定一个字符串，找出其中不含有重复字符的最长子串的长度。此类问题适合使用滑动窗口（双指针）结合哈希集合来高效解决。

第1步：定义窗口与状态集合

使用 Set<Character> 维护当前窗口内的字符。rk 作为右指针，初始为-1；ans 记录最大长度，初始为0。

第2步：移动左指针移除元素

外层循环控制左指针 i 从0开始遍历。当 i 增加时，如果之前窗口内存在 s.charAt(i - 1)，则将其从集合中移除，缩小窗口左边界。

第3步：扩展右指针填充元素

内层 while 循环尝试向右扩展窗口：rk + 1 小于字符串长度且该字符未在集合中出现时，将其加入集合并递增 rk。

第4步：更新最大长度

每次窗口稳定后，计算当前窗口长度 rk - i + 1，并与 ans 取最大值。最终返回 ans。

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Set<Character> occ = new HashSet<Character>();
        int rk = -1, ans = 0;
        for(int i=0;i<s.length();i++){
            if (i != 0) {
                occ.remove(s.charAt(i - 1));
            }
            while(rk+1<s.length()&&!occ.contains(s.charAt(rk + 1))){
                occ.add(s.charAt(rk + 1));
                ++rk;
            }
            ans = Math.max(ans, rk - i + 1);
        }
        return ans;
    }
}

数组中唯一数字之和：计数法优化

计算数组中所有独一无二（只出现一次）的元素之和。由于题目隐含数据范围通常较小（如0-100），可以使用计数数组替代复杂的哈希逻辑。

第1步：统计元素频次

创建长度为101的整型数组 arr，遍历输入数组 nums，将每个数字对应的索引位置计数器加1。例如 nums[i] 的值直接作为 arr 的下标。

第2步：筛选并累加唯一值

遍历计数数组 arr，检查索引 i 处的值是否等于1。若等于1，说明原始数组中数字 i 仅出现一次，将其加入总和中。

class Solution {
    public int sumOfUnique(int[] nums) {
        int sum = 0;
        int[] arr = new int[101];
        for(int i=0;i<nums.length;i++){
            arr[nums[i]]+=1;
        }
        for(int i=0;i<arr.length;i++){
            if(arr[i]==1){
                sum+=i;
            }
        }
        return sum;
    }
}

最大升序子序列和：动态规划思维

找出数组中严格递增的子序列的最大和。这并非简单的全局排序，而是需要识别局部连续的升序段。

第1步：处理边界情况

如果数组只有一个元素，直接返回该元素即可。

第2步：初始化累加器与最大值

sum 记录当前连续升序子序列的和，初始化为第一个元素 nums[0]。max 记录历史最大值，初始化为最小整数，确保第一次比较有效。

第3步：遍历判断升序关系

从第二个元素开始遍历。若 nums[i] > nums[i-1]，说明处于升序过程中，将 nums[i] 加入 sum，并更新 max。若不满足升序，则说明当前升序段结束，先更新 max，然后将 sum 重置为当前元素 nums[i]，开启新的子序列计算。

class Solution {
    public int maxAscendingSum(int[] nums) {
        if(nums.length==1) return nums[0];
        int sum = nums[0];
        int max = Integer.MIN_VALUE;
        for(int i=1;i<nums.length;i++){
            if(nums[i]>nums[i-1]){
                sum +=nums[i];
                max = Math.max(max,sum);
            }else{
                max = Math.max(max,sum);
                sum = nums[i];
            }
        }
        return max;
    }
}